Group Abstract Group Abstract

Message Boards Message Boards

0
|
6.5K Views
|
5 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Sporadic convergence failure: “SingularValueDecomposition::cflsvd”

POSTED BY: John Sidles
5 Replies
POSTED BY: Daniel Lichtblau

In case it's helpful, the code below seems to trigger the same issue.

L = 5;
n = 4;
id = ConstantArray[1, L] // SparseArray // DiagonalMatrix;
D0 = SparseArray[{{i_, j_} /; Mod[j - i, L] == 1 :> 1, {i_, j_} /; Mod[j - i, L] == 0 :> -1}, {L, L}];
Dj[j_] := KroneckerProduct @@ Table[If[i == j, D0, id], {i, n}]
M = Sum[If[a != b != c != d, KroneckerProduct[Dj[b], SparseArray[{a, (c - 1) n + d} -> 1, {n, n^2}]], 0], {a, n}, {b, n}, {c, n}, {d, n}];
svd = M // Normal // N // SingularValueDecomposition;
POSTED BY: Kevin Slagle

The original question has been edited to establish that the SVD "cflsvd" bug is sensitive to the least-significant-bits of MachinePrecision input matrices, which is behavior that no well-conditioned SVD algorithm should exhibit.

POSTED BY: John Sidles

On Mar 11, 2016, near-identical symptoms (namely, SVD convergence-failure) were reported on GitHub's "Anaconda-Issues" forum as "BUG: LinAlgError raised by scipy.linalg.svd for valid matrix #695".

By Apr 26, 2016, Anaconda users reported that:

Great news -- the Intel folks could replicate the issue with the same array 
that Anaconda currently fails on, and they report that it is fixed 
by the current pre-release version of MKL 11.3.3

Here "MKL" is an acronym for (afaict) the "Intel Kernel Library".

However, as of March 9, 2017, Intel users and engineers were still wresting with this problem, as reported in the thread "Bug in GESDD (but not GESVD)". It is not apparent that the source of the SVD failures is understood, much less that a software fix has been implemented.

Conclusion  Multiple lines of evidence seeming establish that an SVD bug exists, that is reproducibly elicited by unremarkable matrices, that has been affecting multiple users, on multiple systems (including Mathematica), for multiple years, whose algorithmic origin(s) are unknown, and for which no software fix(es) are presently available.

POSTED BY: John Sidles

Please note, too, that an effectively unlimited number of convergence-failing matrices can be generated, as it turns out that randomly permuting rows and columns of a numerical matrix that "cflsvd"-fails, sporadically--not invariably---yields a new matrix that similarly "cflsvd"`-fails.

POSTED BY: John Sidles
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard