eigs takes too long to converge

[stevengj]

The code below, which constructs a sparse discrete lapacian (or –laplacian, actually) inside a cylinder and evaluates the smallest eigenvalue using eigs, dies with an ARPACKException for me:

Changing to Nx=Ny=100 works fine. However, Nx=Ny=400 is "only" a 100000x100000 (positive-definite real-symmetric) sparse matrix from a 2d grid (hence the sparse-direct solver should be efficient), and similar code works fine in Matlab.

What does this error mean? cc: @ViralBShah

# construct the (M+1)xM matrix D, not including the 1/dx factor
diff1(M) = [ [1.0 zeros(1,M-1)]; diagm(ones(M-1),1) - eye(M) ]

# sparse version (the lazy way):
sdiff1(M) = sparse(diff1(M))

# make the discrete -Laplacian in 2d, with Dirichlet boundaries
function Laplacian(Nx, Ny, Lx, Ly)
   dx = Lx / (Nx+1)
   dy = Ly / (Ny+1)
   Dx = sdiff1(Nx) / dx
   Dy = sdiff1(Ny) / dy
   Ax = Dx' * Dx
   Ay = Dy' * Dy
   return kron(speye(Ny), Ax) + kron(Ay, speye(Nx))
end

# Define mesh for the cylinder
# Code adapted from lecture notes
Lx = 1
Ly = 1
Nx = 400
Ny = 400
x = linspace(-Lx,Lx,Nx+2)[2:end-1]   # a column vector
y = linspace(-Ly,Ly,Ny+2)[2:end-1]'  # a row vector
r = sqrt(x.^2 .+ y.^2)   # use broadcasting (.+) to make Nx x Ny matrix of radii
i = find(r .< 1)         # and get indices of points inside the cylinder
A = Laplacian(Nx,Ny,2Lx,2Ly)
Ai = A[i,i]              # to make a submatrix for the Laplacian inside the cylinder
λi, Ui= eigs(Ai, nev=1, which="SM")

[ViralBShah: The title was ARPACKException needs better error message, which is fixed.]

[stevengj]

Setting maxiter=10000 in eigs fixes the problem, so I guess it is just converging slowly. But it would be good to have a clearer error message, at least.

[stevengj]

(It would also probably converge faster if there were a way to exploit the fact that my matrix is symmetric positive definite. Related to #30.)

[ViralBShah]

We should certainly give a better message. That is easy to fix.

I don't think there is a way to exploit spd property in arpack - only the fact that it is symmetric.

[stevengj]

If you are doing inverse iteration then you can use Cholesky factorization for SPD matrices.

A basic problem here is that eigs is over-typed. We should do duck-typing: support passing any object (not just an AbstractArray) that supports the necessary operations (size, \, * ?). That way we could pass factorization objects or other abstract linear operations.

[andreasnoack]

It is tempting to think of AbstractMatrix as the objects that support \ and *, cf. Jutho's post at the mailing list. At least as long as it is not clearly defined what AbstractMatrix is.

By the way. Not directly related to this issue but as a consequence of the example of this issue: eigs seems pretty slow. With the laplacian example I get

@time eigs(Ai,nev=1,which="SM")
elapsed time: 457.095567119 seconds (18300352424 bytes allocated)

and with a pure Julia implementation

@time Arnoldi.eigs(Ai, 1, 2000, eps())
elapsed time: 10.058114537 seconds (6387928 bytes allocated)
1-element Array{Float64,1}:
 5.76436

[ViralBShah]

I wonder what is happening. Can you post your implementation? What happens in matlab or octave? @vtjnash fixed some Fortran calling issues which could potentially explain this.

[ViralBShah]

@stevengj we should be able to exploit the spd property for free due to the use of . The polyalgorithm may need some tweaking.

[stevengj]

The memory usage is pretty insane too... 17GiB!

[andreasnoack]

The implementation is here https://gist.github.com/andreasnoackjensen/6963157. I only did it to learn how the Lanczos method works so it is very simple. I have defined A_mul_B! for sparse matrices to be allocation free like gemv which explains the big difference in allocated memory, but not the whole time difference. I tweaked the arnoldi code to use my A_mul_B! instead of * and now I get

julia> @time eigs(Ai,nev=1,which="SM")[1]
elapsed time: 382.070997098 seconds (85137664 bytes allocated)
1-element Array{Float64,1}:
 5.76436

so much of the reallocation is avoided but the timing is still not good. I think I have made Ai to be identical in MATLAB and there I get

>> tic;eigs(Ai,1,'sm');toc
Elapsed time is 3.371547 seconds.

so the difference is huge.

[ViralBShah]

579a005c995df57cd92f0dc90e6bda2b25158de6 gives us a better error message.

[ViralBShah]

@JeffBezanson I have a suspicion that type inference is not working as well as it ought to here, which might be slowing down eigs, by taking a lot of time in the sparse matvec.

[JeffBezanson]

Can you give me an example call that you think runs too slowly?

[andreasnoack]

@stevengj's example above is one. There eigs takes 457 seconds and a Julia implementation of the same calculation takes 5.76 second.

[JeffBezanson]

To narrow it down a bit, should I focus on the product of Ai and a random dense vector?

[JeffBezanson]

Ok, there aren't any type inference problems in sparse matvec. I tried hoisting the accesses to A.colptr etc. but that didn't do very much. (I'm looking at linalg/sparse.jl:14)
We do need some codegen improvements around 1-d arrays, but I don't expect any more than a factor of 2 from that (probably not even that much).