CODEWITHSUNDEEP
matlab
Rhinocerotidae
Rhinocerotidae

Reputation: 925

MATLAB - Eigs(A,B) when B is singular

I am trying to solve an eigenvalue problem of large matrices (8000×8000). Since A and B are sparse in my case, I thought that it is better to use eigs than eig. But the problem is that B is singular and MATLAB's eigs can not handle it.

Are there are any workarounds to solve this problem?

P.S: Both A and B are complex and non-symmetric

Upvotes: 3

Views: 2900

Answers (1)

TroyHaskin
TroyHaskin

Reputation: 8401

The underlying ARPACK routines leveraged by MATLAB allow solution of singular mass matrix problems (B to MATLAB, M to ARPACK). The APRACK documentation states:

If M is singular or if one is interested in eigenvalues near a point σ then a user may choose to work with C = (A - σ M)-1M

where C is the shifted operator. Therefore, by explicitly specifying a numerical value for the shift parameter sigma, eigs can attempt to converge to the nearest dominate eigenvalue as long as the shift doesn't make C singular.

For example, 

>> n = 1000;
>> A = sprandn(n,n,1/n) + speye(n,n); % ensure invertibility of A
>> B = sprandn(n,n,1/n); B(1:n-1,1:n-1) = B(1:n-1,1:n-1) + speye(n-1); % mildly pathological B
>> condest(B)
ans =
   Inf

A doesn't need to be invertible, but it will let us check our answer in a bit. Calling eigs without a specified shift throws an error:

>> eigs(A,B,1)
Error using eigs/checkInputs/LUfactorB (line 954)
B is singular.
...

Specifying a shift remedies this1

>> eigs(A,B,1,0)
ans =
    0.1277

But that's only the dominate eigenvalue found near 0. Let's check some other points

>> sort(arrayfun(@(sigma)eigs(A,B,1,sigma),linspace(-10,10,10).'),'descend')
ans =
   4.1307 + 0.2335i
   4.1307 + 0.2335i
   4.1307 + 0.2335i
   3.3349 + 0.0000i
   1.1267 + 0.0000i
   0.1277 + 0.0000i
   0.1277 + 0.0000i
   0.1277 + 0.0000i
   0.1277 + 0.0000i
   0.1277 + 0.0000i

If looks like 4.1307 + 0.2335i might be the dominate eigenvalue of the system. Let's look around that point for some more eigenvalues:

>> eigs(A,B,5,4.13)
ans =
   4.1307 - 0.2335i
   4.1307 + 0.2335i
   3.3349 + 0.0000i
   2.8805 + 0.0000i
   2.6613 + 0.0000i

Looks good. But are there bigger finite eigenvalues? Luckily, since A is invertible, we can check the eigenvalues directly by taking the reciprocals of eig(B/A):

>> lam = sort(1./eig(full(B/A)),'descend')
lam =
      Inf + 0.0000i
   4.1307 + 0.2335i
   4.1307 - 0.2335i
   3.4829 + 1.6481i
   3.4829 - 1.6481i
   3.3349 + 0.0000i
   2.4162 + 2.1442i
   2.4162 - 2.1442i
   2.8805 + 0.0000i
   2.2371 + 1.7137i
   2.2371 - 1.7137i
   ...

First, we see that annoying infinite eigenvalue giving all the problems. Second, we can see that eigs did find the largest finite eigenvalue but didn't find the slightly smaller magnitude eigenvalues in the complex plane because the purely real eigenvalues were closer to the shift point:

>> [lam,abs(lam-4.13)]
ans =
      Inf + 0.0000i      Inf + 0.0000i
   4.1307 + 0.2335i   0.2335 + 0.0000i % found by eigs(A,B,5,4.13)
   4.1307 - 0.2335i   0.2335 + 0.0000i % found by eigs(A,B,5,4.13)
   3.4829 + 1.6481i   1.7705 + 0.0000i
   3.4829 - 1.6481i   1.7705 + 0.0000i
   3.3349 + 0.0000i   0.7951 + 0.0000i % found by eigs(A,B,5,4.13)
   2.4162 + 2.1442i   2.7450 + 0.0000i
   2.4162 - 2.1442i   2.7450 + 0.0000i
   2.8805 + 0.0000i   1.2495 + 0.0000i % found by eigs(A,B,5,4.13)
   (8 more complex eigenvalues)
   2.6613 + 0.0000i   1.4687 + 0.0000i % found by eigs(A,B,5,4.13)

So yes, there is a workaround. But it requires more work to perform robustly and correctly, which is the norm for problems involving singular matrices.

The "best way", I would say, is that if the problem fits into memory and can be computed directly in a reasonable amount of time, do so. Otherwise, the above shift method can supplement the work with effort.

1 I'll note that not all values of sigma will work. For the example presented above, 1 fails:

>> eigs(A,B,5,1)
Error using eigs/checkInputs/LUfactorAminusSigmaB (line 994)
The shifted operator is singular. The shift is an eigenvalue.
 Try to use some other shift please.

Do to the large number of 1 eigenvalues in the example system, the chosen shift creates a singular C matrix, which is not good. Slightly moving off of this point remedies the error.

Upvotes: 7

Related Questions