Endless loop in eigenvalue calculation

[daingun]

The calculation of the eigenvalues of a matrix leads to an endless loop.
The code and the specific matrix are available in this playground:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=bf7b783d7d993ba5ee18292ef2a62778

The endless loop happens only when the type of the elements is f32, calculation is performed correctly if the type is changed to f64, so it seems a problem of over/underflow.

[daingun]

I had time to debug the issue and i found that the endless loop is the following:

nalgebra/src/linalg/schur.rs

Line 132 in a2b128c

while end != start {

It seems that the function delimit_subproblem keeps returning the same values for the sub tuple

nalgebra/src/linalg/schur.rs

Lines 247 to 250 in a2b128c

	let sub = Self::delimit_subproblem(&mut t, eps, end);
	start = sub.0;
	end = sub.1;

[Andlon]

@daingun: I'm not in a position to address this issue, but I'd just like to say that I appreciate that you've taken the time to look into this!

[alexhroom]

I'd just like to note that delimit_subproblem returning the same values over and over isn't necessarily a problem. take e.g. for the matrix DMatrix::from_row_slice(3, 3, &[1., 2., 3., 4., 5., 6., 7., 8., 9.]);, the start and end are 0, 2 for 4 iterations in a row, but for each of these iterations a change is made to t and after that it drops to 0, 1 and completes.

However for the example given here, the subproblem is 0, 10 for 2 iterations and then becomes 4, 10 - after this the matrix t doesn't change at all and gets stuck at

  ┌                                                                                                                                                                                                                                                                                                                                                      ┐
  │               0.00000005033005                   -0.008609546                    0.038023666                     0.18105564                  0.00015394263                 -0.00028078497                  -0.0015527399                  -0.0115151685                   -0.107716076                     -0.2981016                      1.0001383 │
  │      0.00000000000000014454559              0.000000023516739              -0.00000010358409               -0.0000004942107           -0.00000000042151233             0.0000000007619917             0.0000000042020214              0.000000031433622               0.00000029346796                 0.000000808347                -0.000002718418 │
  │                              0             0.0000000070449397              -0.00000003196059                -0.000000148921           -0.00000000012240672            0.00000000024413305             0.0000000013842567               0.00000000946614               0.00000008996139                0.0000002615884               -0.0000008564876 │
  │                              0                              0            0.00000000043556236              0.000000004981259           0.000000000005560113          -0.000000000021723326           -0.00000000017046922           -0.00000000031183311             -0.000000009431206              -0.00000001663141              0.000000071853734 │
  │                              0                              0                              0                              0      -0.0000000000000015101744      -0.0000000000000139757285        -0.00000000000012050238       0.0000000000000054270036           -0.00000000000399593           -0.00000000001278469           0.000000000040097592 │
  │                              0                              0                              0                              0        -0.00000000000014644587    0.0000000000000000015051459      0.00000000000000001154493    0.0000000000000000043176342       0.0000000000000007054399      0.00000000000000058523666      -0.0000000000000042783884 │
  │                              0                              0                              0                              0                              0         0.00000000000014644339    -0.000000000000000018902619    0.0000000000000000008772947      -0.0000000000000006288283      -0.0000000000000020054437        0.000000000000006327595 │
  │                              0                              0                              0                              0                              0                              0         0.00000000000014644559 -0.000000000000000000012728166    -0.000000000000000014310413   -0.0000000000000000006406586  0.000000000000000000096476175 │
  │                              0                              0                              0                              0                              0                              0                              0         0.00000000000014644555    -0.000000000000000055278905    -0.000000000000000003896652   -0.0000000000000000002880686 │
  │                              0                              0                              0                              0                              0                              0                              0                              0         0.00000000000014481493      -0.0000000000000003584098       0.0000000000000069841907 │
  │                              0                              0                              0                              0                              0                              0                              0                              0                              0        -0.00000000000014641638     0.000000000000000016707761 │
  └                                                                                                                                                                                                                                                                                                                                                      ┘

Note this issue is also in #611 and #1528

[Toucan4Life]

Closing #1565 seems to have stopped the endless loop for this matrix. I get eigenvalues:

Index	Real	Imaginary
0	-380.1543744543736	0.0
1	-20.285847352842318	69.35518375481293
2	-20.285847352842318	-69.35518375481293
3	-6.069628119917628	68.34274128342743
4	-6.069628119917628	-68.34274128342743
5	-2.207304494039617	6.556731759603767
6	-2.207304494039617	-6.556731759603767
7	-1.3634045511691908	3.5460647570849866
8	-1.3634045511691908	-3.5460647570849866
9	-0.09637569405926044	0.020021460242567943
10	-0.09637569405926044	-0.020021460242567943