Sublinear Complexity of Krylov Subspace Method for Kronecker Product Matrices

Ilgis Ibragimow

In this work we discuss a new Krylov subspace methods for the matrices presented as the sum of Kronecker products of matrices. Those matrices arising in the FEM problem for the tensor product meshes.

The main result is that those methods require O(N2/d) memory words and arithmetic complexity, where d is the dimension of the mesh, so, for 3D problem we observe a sublinear complexity. For those methods we prove the convergence.

The software package for those methods were developed and we test those methods for the solution of linear systems and eigenvector solvers and confirm the convergence and sublinear complexity.