Re: Diagonalizing large sparse matrices
- To: mathgroup at smc.vnet.net
- Subject: [mg116647] Re: Diagonalizing large sparse matrices
- From: Oliver Ruebenkoenig <ruebenko at wolfram.com>
- Date: Tue, 22 Feb 2011 06:25:02 -0500 (EST)
On Mon, 21 Feb 2011, Mikhail Lemeshko wrote:
> On Feb 16, 12:45 pm, Oliver Ruebenkoenig <ruebe... at wolfram.com> wrote:
>> Hello Mikhail,
>>
>>
>>
>> On Wed, 16 Feb 2011, MikhailLemeshkowrote:
>>> Dear friends,
>>
>>> Are there any ways to speed up the Eigenvalues[] problem for large
>>> sparse matrices (those I have are about 15000x15000)?
>>
>>> I need only the first eigenvalue (which is usually negative), here is
>>> the code fragment:
>>
>>> e0=Parallelize[-Eigenvalues[N[matr], 1, Method -> {Arnoldi, Criteria -
>>>> RealPart}]]
>>
>>> (I have a 2 core processor)
>>
>>> Many thanks in advance!
>>
>>> Misha
>>
>> Parallelize will be of no use here - the parallelization happens inside the
>> Eigenvalues. Try something like
>>
>> m = 15000;
>> s = SparseArray[{{i_, i_} -> -2., {i_, j_} /; Abs[i - j] == 1 ->
>> 1.}, {m, m}];
>>
>> (*s=SparseArray[N[matr]]*)
>>
>> Eigenvalues[s, 1, Method -> {Arnoldi}]
>>
>> Oliver
>
> Thank you a lot.
>
> If I do s=SparseArray[N[matr]], the diagonalization becomes much
> faster indeed.
>
> However there is another problem: I have an analytical matrix in a
> loop, diagonalizing it for different values of parameters. And
> substitution of parameters' values there, and then making a sparse
> array out of it takes a lot of time, since the matrix is huge.
Here a some random thoughts. If your matrix is largely sparse, it might be
beneficial to not test for every entry in that matrix but to find the
general pattern of that matrix and then use Band.
Another idea is to generate the matrix as before and then extract the non
zero positions and the non zero values such as here
nzPos = HTotalmatr["NonzeroPositions"];
nzVals = HTotalmatr["NonzeroValues"];
The you make the first replacement
nzVals2 = nvVals /. {whatever ->...}
And in the loop the second one
nzVals3 = nvVals2 /.{...->...}
You can then generate a new SparseArray with
SparseArray[nzPos -> Developer`ToPackedArray[N[nzVals3]]]
and use that to find the Eigenvalues.
Two notes:
- The reason that SparseArray /. {->} does "not work" is that
AtomQ[HTotalmatr] is True
- Parallelize[ For[... Eigenvalues[...] ] ] will not help much. Eigenvalues
does the parallelization itself on the BLAS level which is quite optimal.
I hope this gives some new ideas ho you could tackle your computation.
Oliver
>
> Making an analytical sparse array and then substituting the parameters
> there doesn't seem to work, and the Mathematica 8 documentation on the
> SparseArray[] functions is kind of scarce...
>
> Thank you again.
>
> Misha
>
>