ENH: scipy.linalg.eigsh cannot get all eigenvalues #7004

amanp10 · 2017-02-04T18:43:52Z

Fixes: #6430
unit tests and warnings added along with the changes.

perimosocordiae

This PR broke the test_arpack.test_eigen_bad_kwargs test.

My other comments are in-line.

perimosocordiae · 2017-02-07T18:20:42Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+    eigsh(A, k=4)
+    eigsh(A, k=5)
+
+


Each of these tests should check the returned values of eigs/eigsh for correctness.

perimosocordiae · 2017-02-07T18:21:37Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+    if k >= n:
+        import warnings
+        warnings.warn('k greater than/equal to the order of the square '
+                      'matrix. Using scipy.linalg.eig instead.')


This should use a SparseEfficiencyWarning rather than a generic UserWarning.

perimosocordiae · 2017-02-07T18:22:17Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        import warnings
+        warnings.warn('k greater than/equal to the order of the square '
+                      'matrix. Using scipy.linalg.eig instead.')
+        if return_eigenvectors is True:


The is True isn't needed here.

perimosocordiae · 2017-02-07T18:26:30Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+    if k >= n-1:
+        import warnings
+        warnings.warn('k greater than/equal to N - 1 . '
+                      'Using scipy.linalg.eig instead.')


This warning doesn't explain what N is.

amanp10 · 2017-02-09T16:48:52Z

The reason test_arpack.test_eigen_bad_kwargs broke was because now k more than N-1 wont raise any ValueError instead it would go on to eig. Earlier, since k=6 is default, ValueError was raised. I think test_arpack.test_eigen_bad_kwargs needs to be modified little.

pv · 2017-02-09T22:35:19Z

@amanp10: correct, test_eigen_bad_kwargs should probably be modified to use a larger matrix.

amanp10 · 2017-02-10T13:34:37Z

@perimosocordiae please have a look.

perimosocordiae

Looks fine to me now.

This may have backwards-compatibility implications, though, so it should probably get a mention in the release notes.

perimosocordiae · 2017-02-10T22:37:27Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        if return_eigenvectors:
+            return eig(A.todense())
+        else:
+            return eig(A.todense(), right=False)


These can probably be condensed into one return:

return eig(A.todense(), right=return_eigenvectors)

(Same for the similar lines below.)

amanp10 · 2017-02-11T08:52:09Z

Am I supposed to mention it in the release notes or the core-devs do it?

pv · 2017-02-11T14:11:27Z

@amanp10: note that you should not do git merge upstream/master or git pull upstream/master etc in pull requests. (If there are conflicts, the PR should be rebased on master instead of master being merged to the PR.)

amanp10 · 2017-02-11T19:54:29Z

@pv I will take care from now on. Thanks for pointing out.

pv · 2017-02-11T19:59:34Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        warnings.warn('k greater than/equal to N - 1 for N * N square matrix. '
+                      'Using scipy.linalg.eig instead.',
+                      SparseEfficiencyWarning)
+        return eig(A.todense(), right=return_eigenvectors)


This should also check if M is given, and if yes, solve the generalized eigenvalue problem. (Add also a test.)

Additionally A may be a LinearOperator or a dense matrix, which don't have a todense method.

amanp10 · 2017-02-20T06:13:11Z

@pv Sorry for the late commit. I got busy with class tests. Please have a look

perimosocordiae · 2017-02-20T15:15:27Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        if not isdense(A):
+            A = A.todense()
+
+        return eig(A, b=M, right=return_eigenvectors)


~~This should be eigh, right?~~
My bad, this is fine.

Sorry for the mistake, I will correct it.

amanp10 · 2017-03-02T07:30:25Z

I was wondering if it would be necessary to add tests for complex or complex-hermitian matrix as well?

…anch2

perimosocordiae · 2017-08-15T13:46:57Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+
    n = A.shape[0]

+    if k >= n - 1:


This condition should be run after the k <= 0 or k >= n check.

perimosocordiae · 2017-08-15T13:47:52Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        import warnings
+        warnings.warn('k greater than/equal to N - 1 for N * N square matrix. '
+                      'Using scipy.linalg.eig instead.',
+                      SparseEfficiencyWarning)


A SparseEfficiencyWarning doesn't make sense if A isn't sparse.

perimosocordiae · 2017-08-15T13:49:00Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+            raise ValueError("'M' cannot be a LinearOperator since"
+                             "scipy.linalg.eig is being used.")
+        if not isdense(A):
+            A = A.todense()


I'd prefer raising an error if A is sparse, with a hint to call .toarray() first if that's actually what the user wants.

I think the docs need to be changed as they mention A as A : ndarray, sparse matrix or LinearOperator. Or should we let it be with errors and warnings wherever necessary?

No, we still need to support all three input types. I'm suggesting that be behavior for non-ndarray types (spmatrix, LinearOperator) remain as it was before this PR, but with an informative error message so that the user knows how to proceed.

Okay. I get it.

perimosocordiae · 2017-08-15T13:51:35Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+    if k >= n:
+        import warnings
+        warnings.warn('k greater than/equal to N for N * N square matrix. '
+                      'Using scipy.linalg.eig instead.',


scipy.linalg.eigh, here and in the error messages below.

perimosocordiae · 2017-08-15T13:52:40Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+                             "scipy.linalg.eig is being used.")
+        if isinstance(M, LinearOperator):
+            raise ValueError("'M' cannot be a LinearOperator since"
+                             "scipy.linalg.eig is being used.")


These errors should explain that k >= n is why we can't use eigsh here.

perimosocordiae · 2017-08-15T13:54:49Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+        j = np.random.randint(N, size=N * N // 2)
+        M[i,j] = 0
+
+    M = 0.5 * (M + M.T)  # Make M symmetric


This is likely to destroy whatever sparsity we just created. I'd symmetrize first, then set (symmetric) zeros.

perimosocordiae · 2017-08-15T13:55:48Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+    if pos_definite:
+        M = M + N * np.eye(N)
+
+    return M


Need to create an actual sparse matrix if sparse=True.

perimosocordiae · 2017-09-11T13:35:29Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+        raise ValueError("k=%d must be greater than 0." % (k, n - 1))
+
+    if k >= n - 1:
+        if not isdense(A):


Why not use if issparse(A) here?

perimosocordiae · 2017-09-11T13:36:08Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

 from scipy.linalg import svd, hilbert

 from scipy._lib._gcutils import assert_deallocated
+#from warnings import catch_warnings, simplefilter


Remove this line, please.

perimosocordiae · 2017-09-11T13:37:13Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+            i = np.random.randint(N, size=N * N // 2)
+            j = np.random.randint(N, size=N * N // 2)
+            M[i, j] = 0
+        M = M + Id


perimosocordiae · 2017-09-11T13:37:59Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+            j = np.random.randint(N, size=N * N // 2)
+            M[i, j] = 0
+
+    return M


if sparse: M = scipy.sparse.csr_matrix(M) return M

perimosocordiae · 2017-09-11T13:39:34Z

scipy/sparse/linalg/eigen/arpack/tests/test_arpack.py

+    A = generate_matrix(4, sparse=False)
+    M1 = np.random.random((4, 4))
+    M2 = generate_matrix(4, sparse=True)
+    M3 = aslinearoperator(M1)


Might be clearer to use M_dense, M_sparse, and M_linop.

perimosocordiae · 2017-10-08T15:21:27Z

scipy/sparse/linalg/eigen/arpack/arpack.py

-        raise ValueError("k=%d must be between 1 and ndim(A)-1=%d"
-                         % (k, n - 1))
+    if k <= 0:
+        raise ValueError("k=%d must be greater than 0." % (k, n - 1))


You're giving too many values to the format string here. We aren't using n - 1 anymore.

perimosocordiae · 2017-10-08T15:22:33Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+                            "A with k >= N - 1.")
+        if isinstance(M, LinearOperator):
+            raise TypeError("Cannot use scipy.linalg.eig for LinearOperator "
+                            "M with k >= N - 1.")


This LinearOperator checks need to happen before the warning.

I think we should inform the user that we are using or trying to use scipy.linalg.eig right after the check k >= n(or k >= n - 1). Or maybe we can put it in the docs somewhere.

Ok, I see what you're saying here. (Sorry for the long wait!) Can you move the warning up before the TypeError checks here? And maybe have it say "Attempting to use" instead of "Using"?

amanp10 · 2017-12-03T05:15:15Z

I need some help here. I cant figure out why the build is failing.

andyfaff · 2017-12-03T05:20:36Z

THe build is failing due to issues we've been having with our OSX image on TravisCI. I think the problem is unrelated to this PR.

amanp10 · 2017-12-03T06:04:27Z

@perimosocordiae I have made the changes please have a look.

perimosocordiae · 2017-12-03T21:54:16Z

Looks good now, thanks @amanp10! I'll wait a bit to let others comment before merging.

amanp10 · 2017-12-04T03:05:27Z

Thank you for all the reviews.

ilayn · 2017-12-04T03:18:40Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+            raise TypeError("Cannot use scipy.linalg.eig for LinearOperator "
+                            "M with k >= N - 1.")
+
+        import warnings


You just need to import warnings module at the top of the file and you can use it in any function. Also with

from .misc import LinAlgWarning

you can raise a LinAlgWarning which I guess is more relevant instead of a UserWarning. Also you already know the values of k and N so the message can use those values

warnings.warn("{0} >= {1} for {1}x{1} square matrix. " "Using scipy.linalg.eigh instead.".format(k, N), LinAlgWarning, stacklevel=3)

I cant find LinAlgWarning because this branch has not been updated to v1.1. Should I merge this branch with the latest master branch to get LinAlgWarning?

Then I guess the regular RuntimeWarning would suffice. At some point we will sweep all the warnings anyhow.

ilayn · 2017-12-04T03:19:12Z

scipy/sparse/linalg/eigen/arpack/arpack.py

+            raise TypeError("Cannot use scipy.linalg.eigh for LinearOperator "
+                            "M with k >= N.")
+
+        import warnings


same import issue as above

ilayn · 2018-01-20T13:04:13Z

@pv @perimosocordiae Any reservations left for this PR?

perimosocordiae · 2018-03-07T15:14:44Z

Sorry for the extreme slowness on my part. I left one comment, and there appears to be a merge conflict to resolve, but after those are handled I will definitely merge this quickly.

amanp10 · 2018-03-08T08:35:32Z

I am unable to understand why the Travis-Ci build is failing. Need some help here.

rgommers · 2018-03-08T16:12:59Z

Just ignore those TravisCI failures, that's due to some issues unrelated to this PR

perimosocordiae · 2018-03-09T17:26:30Z

Merged, at long last. Thanks, @amanp10 !

amanp10 · 2018-03-10T05:09:10Z

I am happy I contributed something.

ENH: scipy.linalg.eigsh cannot get all eigenvalues

ENH: scipy.linalg.eigsh cannot get all eigenvalues

4ed7817

perimosocordiae requested changes Feb 7, 2017

View reviewed changes

ENH: scipy.linalg.eigsh cannot get all eigenvalues

e805202

amanp10 added 2 commits February 10, 2017 12:17

ENH: scipy.linalg.eigsh cannot get all eigenvalues

dabcc89

Merge remote-tracking branch 'upstream/master' into Branch2

687b4aa

perimosocordiae approved these changes Feb 10, 2017

View reviewed changes

amanp10 added 2 commits February 11, 2017 18:47

ENH: scipy.linalg.eigsh cannot get all eigenvalues

37dbae5

Merge remote-tracking branch 'upstream/master' into Branch2

9c64b19

pv reviewed Feb 11, 2017

View reviewed changes

rgommers added good first issue Good topic for first contributor pull requests, with a relatively straightforward solution scipy.sparse.linalg labels Feb 16, 2017

pv added the needs-work Items that are pending response from the author label Feb 18, 2017

ENH: scipy.linalg.eigsh cannot get all eigenvalues

bad0e32

perimosocordiae reviewed Feb 20, 2017

View reviewed changes

ENH: scipy.linalg.eigsh cannot get all eigenvalue

0b2583d

amanp10 added 3 commits May 25, 2017 22:12

Resolving Conflicts

bcb1862

Merge branch 'master' of https://www.github.com/amanp10/scipy into Br…

e8d24a0

…anch2

Merge branch 'master' into Branch2

9ff77c5

perimosocordiae requested changes Aug 15, 2017

View reviewed changes

amanp10 added 3 commits September 5, 2017 00:58

Sparse Matrix 'A' behaviour

e883a45

Fixed build errors

3c7fc8c

Fixed build errors

013e1bc

perimosocordiae requested changes Sep 11, 2017

View reviewed changes

Review changes

84eb125

perimosocordiae requested changes Oct 8, 2017

View reviewed changes

Review changes

3d0a942

perimosocordiae approved these changes Dec 3, 2017

View reviewed changes

ilayn reviewed Dec 4, 2017

View reviewed changes

Review Changes

55dcc1d

amanp10 added 3 commits March 8, 2018 12:55

Merge branch 'master' into Branch2

442ad24

Moved up the added warning, before tests

4af2b53

Merge branch 'Branch2' of https://github.com/amanp10/scipy into Branch2

b86ca2a

removing extra import

5cf9122

perimosocordiae merged commit 5a6fad5 into scipy:master Mar 9, 2018

amanp10 deleted the Branch2 branch March 10, 2018 05:09

adbugger pushed a commit to adbugger/scipy that referenced this pull request Mar 11, 2018

ENH: scipy.linalg.eigsh cannot get all eigenvalues (scipy#7004)

dd58473

ENH: scipy.linalg.eigsh cannot get all eigenvalues

pv added this to the 1.1.0 milestone Mar 17, 2018

perimosocordiae mentioned this pull request May 18, 2018

Travis build failing scikit-learn-contrib/metric-learn#93

Closed

ghost mentioned this pull request Jan 17, 2019

Sparse matrices handler Vibration-Testing/vibrationtesting#20

Closed

sethtroisi mentioned this pull request May 13, 2020

max rank in sparse.linalg.eigsh #4935

Closed

Uh oh!

ENH: scipy.linalg.eigsh cannot get all eigenvalues #7004

ENH: scipy.linalg.eigsh cannot get all eigenvalues #7004

Uh oh!

Conversation

amanp10 commented Feb 4, 2017

Uh oh!

perimosocordiae left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

amanp10 commented Feb 9, 2017

Uh oh!

pv commented Feb 9, 2017

Uh oh!

amanp10 commented Feb 10, 2017

Uh oh!

perimosocordiae left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

amanp10 commented Feb 11, 2017

Uh oh!

pv commented Feb 11, 2017

Uh oh!

amanp10 commented Feb 11, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

amanp10 commented Feb 20, 2017

Uh oh!

perimosocordiae Feb 20, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

amanp10 commented Mar 2, 2017

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

amanp10 Aug 24, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

perimosocordiae Feb 20, 2017 •

edited

Loading

amanp10 Aug 24, 2017 •

edited

Loading

amanp10 Oct 8, 2017 •

edited

Loading