Efficient matrix preconditioners for black box linear algebra (Q1348088)

The authors study preconditioners for black box linear algebra algorithms. The preconditioning allows the reduction of problems to the computation of minimal polynomials, the goal is to ensure good geometrical or algebraic properties of matrices, rather than numerical ones, so condition numbers are not addressed. Preconditioners studied in the paper apply to matrices over an arbitrary field, but the authors focused on matrices over a finite field. The problems considered are the computation of: the minimal polynomial of a matrix, a nonzero vector in the kernel of the matrix, the solution of a linear system, the determinant and the rank of the matrix. Most of the solutions are randomized. The objective is to find algorithms with requires at most \(n(\log n)^{O(1)}\) black box calls, \(n^2 (\log n)^{O(1)}\) additional operations in the entry field and using \(n(\log n)^{O(1)}\) intermediate storage. Then the preconditioning problem is defined and problems in the main three types (linear independence, nilpotent block and cyclicity) are described. Results for the use of diagonal preconditioners to determine nilpotency and characteristic polynomial properties of the matrix are proved. There is also proved how the use of Toeplitz preconditioners can help to obtain a preconditioned matrix with squarefree minimal polynomial with some probability (which depends on the cardinality of the subset where entries for the preconditioning matrices are choosen). Other preconditioners based on butterflies are used for the problem of localizing linear independence. Networks introduced in the paper are not limited to powers of \(2\), and work for arbytrary \(n\), in addition some savings in the arithmetical cost are achieved. Finally sparse preconditioners work on obtaining a matrix without nilpotent blocks of size greater than 1 in its Jordan canonical form, are presented.