-
Notifications
You must be signed in to change notification settings - Fork 123
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Error -9999 with dnaupd
in ARPACK 3.6 for a matrix that worked with ARPACK 3.5
#142
Comments
@caliarim rings a bell ? thanks |
I think I know what is happening. Can you modify your plain C file (not octave) and solve a generalized problem with the silly matrix M = identity? I think it will fail, both with 3.5.0 and 3.6.0. |
Yes, you are correct; modifying the C source to solve a generalized problem with M = identity makes the computation fail both in 3.5.0 and in 3.6.0. Attached is my C code (which is a crude modification of |
I hoped I was wrong. It means there is a long standing bug in Arpack with rank deficient matrices. It cannot compute a Krylov basis of length ncv, since with my patch (or in the generalized case, even before my patch) the initial vector is in the range of the operator (of dimension < ncv). Arpack tries to change the initial vector some times, but it is always in the range of the operator. After some attempts, it failes with info = -9999. I see two possibilities: 1) take the initial vector in the range of the operator only the very first time: any further attempt should not do it or 2) if after some attempts it is not possible to build a basis of length ncv, guess that the matrix is rank deficient and stop to compute the basis, instead of failing. I will need some time to reproduce the problem in fortran77 and try these (or other) possible solutions. Unfortunately, I do not see a workaround in the meantime. |
Thanks for the quick response! I am not familiar with the internals of the algorithm implemented in ARPACK, but based on my limited understanding, implementing option 1 would take us back to where we was with ARPACK 3.5 if the matrix is rank-deficient, while keeping the benefits of the proposed change in all other cases. This would suit me but I was wondering whether this would affect the correctness of the result; if the result is likely to be incorrect with this workaround, I'd rather be on the safe side even if it means that I need to wait more. |
Can you try if the following change
? Thanks |
I have tested the patch above - it fixes the problem and the failing test cases in igraph. Thanks a lot! |
All the previous tests in ARPACK pass, too. ntamas, I see in your last post here igraph/igraph#1107 that there is still one failing test. Is it related to my previous commit, too? |
Nope, I need to fix that; that particular test case is probably unrelated. ARPACK returns eigenvectors that are -1 times the "old" eigenvectors that previous versions returned, and the test case in igraph is too strict and does not ignore the sign. I only need to update the test case to make everything pass. |
My previous patch has a problem in the generalized case. It should be
|
Re-tested the failing test cases in igraph with the new version and it works equally well, FYI. |
Okay, I spoke too soon; I was checking that one single remaining test case failure in igraph, and it turns out that it also fails for ARPACK 3.6 but not for ARPACK 3.5, and the cause of the failure can also be narrowed down to the same commit that caused the original issue reported here. The test case in igraph attempts to find the three eigenvectors with the largest imaginary part in the following 10x10 matrix (generated randomly with a pre-determined seed so it's the same with every test run):
Using The eigenvector reported by LAPACK in Octave is as follows:
ARPACK reports the following values in the 3rd and 4th columns of the eigenvector memory area (first and second columns are for the correct eigenpair, 3rd and 4th belong to the next eigenpair):
This is parallel to the eigenvector reported by LAPACK in Octave only if you swap the two columns and then negate the first column (or, alternatively, if you take the complex conjugate and then swap the real part with the imaginary one). The same test case in igraph also tests |
no, the two eigenvectors are parallel, they differ by a complex multiplicative constant. |
Indeed; sorry for the noise! |
@ntamas: do you confirm that all your tests now pass? I'm going to make a pull request. |
Yes, all test cases pass now, thanks for your efforts! |
Am I write that this change, as others, is not ported to pARPACK? |
It seems, would be great to do it too!
S
|
I am afraid to reopen this issue, but arpack fails once more with identity matrices. One just needs to change
|
The easiest way to test this issue is with GNU Octave 4.4.0 linked to ARPACK 3.6, but the same problem can be reproduced from C as well. The matrix is the PageRank matrix of an undirected star graph with 11 vertices and damping = 0.85:
The matrix has three eigenvalues: 1, -0.85 and 0 (multiplicity = 9). Asking Octave to obtain the dominant eigenvalue with
eigs
(which in turn usesdnaupd
) yields an error:(Related issue: igraph/igraph#1107 )
I know that the multiplicity of the zero eigenvalue could be a problem here; however, note that this matrix worked just fine with ARPACK 3.5 and a simple power iteration also converges to the correct dominant eigenvector. I managed to narrow the source down to this single line of code, but if my understanding is correct, then this line is actually necessary for the referenced patch to work.
Is there anything I am missing here?
(For what it's worth, I have also managed to reproduce the problem by modifying the
matVec
function inTESTS/bug_1315_double.c
to perform the multiplication with the matrix described above. Note that the test case currently does not check the value ofinfo
after runningdnaupd
so the error goes unnoticed by the test case, but I have verified thatinfo
is-9999
in the test case. Let me know if you need my modified plain C code to test this).The text was updated successfully, but these errors were encountered: