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 <donaldrexplanal...@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 <j...@jedbrown.org> > Sent: Friday, January 17, 2025 12:10 AM > To: Matthew Knepley <knep...@gmail.com>; Barry Smith <bsm...@petsc.dev> > Cc: petsc-users@mcs.anl.gov <petsc-users@mcs.anl.gov>; Donald Planalp > <donaldrexplanal...@outlook.com> > Subject: Re: [petsc-users] KSP with large sparse kronecker product > > Matthew Knepley <knep...@gmail.com> writes: > >> On Thu, Jan 16, 2025 at 6:26 PM Barry Smith <bsm...@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.
