Adapt EigenDecomposition implementation

[Aast12]

Implements the Implicit QL Algorithm also used by the EigenDecomposition class using SystemDS data structures. Note this assumes the matrix is symmetric and fits in 1 block of a DenseBlock. The later is also assumed by the current computeEigen function so the only missed functionality is the support for non-symmetric matrices. The implementation focused on reducing as much allocations as possible to match and exceed the performance of the current eigen decomposition function across most cases.

As an initial benchmark, a test was run with Symmetric Positive Definite and tridiagonal (symmetric) matrices of sizes 100x100, 500x500 and 1000x1000. The following table shows the test cases and amount of iterations done per test.

Test case	Iterations
spdTest100	300
spdTest500	100
spdTest1000	30
tridiagonalTest100	300
tridiagonalTest500	100
tridiagonalTest1000	30

What follows are the results of the benchmark, showing an average improvement of 48.95 % across all cases with highest improvements in the largest matrices of 1000x1000 size, with up to a 83% improvement.

#	Instruction	Iterations	Time(s) Old	Time(s) New	Improvement
1	eigen	3060	631.230	423.791	48.95 %
2	tridiagonalTest500	500	201.269	143.769	40.00 %
3	spdTest500	500	185.826	138.117	34.54 %
4	tridiagonalTest1000	30	129.213	70.370	83.61%
5	spdTest1000	30	108.221	66.619	62.44%
6	spdTest100	1000	4.075	2.840	43.48%
7	tridiagonalTest100	1000	3.470	3.088	12.37%

[Baunsgaard]

Hi!

A good start of the PR. I suggest you try to squash your commits. And then afterwards rebase your changes on master.

That should fix your merge conflict.

[Aast12]

Hi!

A good start of the PR. I suggest you try to squash your commits. And then afterwards rebase your changes on master.

That should fix your merge conflict.

It should be fixed now

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 86.03352% with 25 lines in your changes missing coverage. Please review.

Please upload report for BASE (main@6a3ff8c). Learn more about missing BASE report.

Files	Patch %	Lines
...ache/sysds/runtime/matrix/data/LibCommonsMath.java	86.03%	12 Missing and 13 partials :warning:

Additional details and impacted files

@@           Coverage Diff           @@
##             main    #2038   +/-   ##
=======================================
  Coverage        ?   68.80%           
  Complexity      ?    40731           
=======================================
  Files           ?     1440           
  Lines           ?   161743           
  Branches        ?    31461           
=======================================
  Hits            ?   111282           
  Misses          ?    41388           
  Partials        ?     9073           

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[Baunsgaard]

Also feel free if you address any comments, to close or resolve the comments.

[Baunsgaard]

just FYI, some tests are flaky when run in the cloud, therefore if the tests fail, and they are obviously not related to your changes no worries.