The universal block Lanczos-Padé method for linear systems over large prime fields (Q1708252)

The goal of this article is to give a precise overview of the universal block Lanczos-Padé method for solving large sparse linear systems over finite fields with a large number of elements. The approach to the computation of an \(A\)-orthogonal basis based on Padé approximations has advantages from the viewpoint of parallel computations. The authors study the computational complexity of the universal Lanczos-Padé algorithm. With very precise technique it is shown that: - The universal method complexity is \(O \left (pn^2+\frac{n^2K}{q}+nK^2\right )\); - the parallel complexity is \(O \left (\frac{pn^2}{K}+\frac{n^2}{q}+nK\right )\). The work is written on an extremely professional level and represents a certain interest for the specialists working in this everlasting subject.