[petsc-users] KSP with large sparse kronecker product

[Jed Brown]

The "fast diagonalization" or tensor product approach has been heavily used over the years. It's described algebraically in Lynch, Rice, and Thomas (1964) https://urldefense.us/v3/__https://doi.org/10.1007/BF01386067__;!!G_uCfscf7eWS!ZCELMydz5gWkx2Gt3I4wkzt44DArUNpXYqhODuQ4wF6sPEQDSsFeVGdkUQp_vqllE7Z_Z75RnAb-qgfoGFQ$  (see eq 3.8).

Inverses of anything interesting are dense, and scalable preconditioners generally need to provide a dense action (though they can be constructed from sparse parts).

If the pieces of the Kronecker product are of size 1000, then the dense matrix of eigenvectors is only a few MB. If you lots bigger, dense matrices of eigenvectors become intractable, though sometimes you can approximate such things or use fast transforms.

Kronecker products are fun and powerful. Forming them into a naive sparse matrix can be useful for checking correctness and investigating properties, but I think it's rarely the most efficient algorithm.

Donald Planalp <donaldrexplanalpjr at outlook.com> writes:

> Hello,
>
> Currently I am using the block Jacobi preconditioner, and it's the only one which seems to give fast convergence for this problem so far. I actually did implement a matshell which redundantly stored each matrix on each rank (which was far less memory than explicitly storing the Kronecker product) and computed the action of the Kronecker product in a semi-matrix-free way, however without the preconditioner the solver time was far too slow. Unfortunately, I forgot to make a backup of that matshell otherwise I would provide the code for it.
>
> As far as the inverse goes, do you mean inverting the small matrices and then embed them in the larger Kronecker structure such that we have the inverse matrix of the linear system? I'm a bit confused because wouldn't the inversion of the entire large matrix not only break the sparsity pattern inside the blocks, but also the block sparsity? I imagine this would also still use quite a bit of memory. However if I am mistaken I apologize.
>
> I appreciate the quick replies,
> Rex Planalp
> ________________________________
> From: Jed Brown <jed at jedbrown.org>
> Sent: Friday, January 17, 2025 12:10 AM
> To: Matthew Knepley <knepley at gmail.com>; Barry Smith <bsmith at petsc.dev>
> Cc: petsc-users at mcs.anl.gov <petsc-users at mcs.anl.gov>; Donald Planalp <donaldrexplanalpjr at outlook.com>
> Subject: Re: [petsc-users] KSP with large sparse kronecker product
>
> Matthew Knepley <knepley at gmail.com> writes:
>
>> On Thu, Jan 16, 2025 at 6:26 PM Barry Smith <bsmith at petsc.dev> wrote:
>>
>>>
>>>    I don't think we have good code for this case. But it is a good case
>>> and we should definitely provide support so it would be great to talk
>>> about.
>>>
>>>   Possibly start with the name :-) MATSKAIJ :-)
>>>
>>
>> Are you using any preconditioner? If not, you could just use a MATSHELL,
>> and compute the action of your Kronecker matrix.
>
> Also note that if each panel of the Kronecker product is small enough to solve an eigenproblem, you may want to use fast diagonalization to compute an exact inverse. The eigenproblem will have a dense solution (even though the matrix is sparse), but a few dense eigenproblems of size a hundred or thousand could be faster than solving iteratively with systems in the millions.