Efficient matrix preconditioners for black box linear algebra
type: Item
instance of: scholarly article
title: Efficient matrix preconditioners for black box linear algebra
zbMATH Open document ID: 0997.65073
DOI: 10.1016/S0024-3795(01)00472-4
author: Li Chen
author: Wayne Eberly
author: B. David Saunders
author: William J. Turner
author: Gilles Villard
author: Erich L. Kaltofen
published in: Linear Algebra and its Applications
publication date: 2002-05-15T00:00:00Z
review text: 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.
reviewed by: J. Mas
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 15A21
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A12
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 15A15
zbMATH DE Number: 1741658
zbMATH Keywords: matrix preconditioners
zbMATH Keywords: black box algorithms
zbMATH Keywords: sparse matrix
zbMATH Keywords: preconditioning
zbMATH Keywords: condition numbers
zbMATH Keywords: finite field
zbMATH Keywords: minimal polynomial
zbMATH Keywords: linear system
zbMATH Keywords: determinants
zbMATH Keywords: rank
zbMATH Keywords: Jordan canonical form
zbMATH Keywords: nilpotent block
zbMATH Keywords: linear dependence
zbMATH Keywords: cyclicity
MaRDI profile type: Publication
cites work: The rank of sparse random matrices over finite fields
cites work: Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
cites work: A probabilistic remark on algebraic program testing
cites work: Q4227001
cites work: Q4226959
cites work: Q4375610
cites work: Q4226997
cites work: Q4232484
cites work: Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
cites work: Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
cites work: Q4227349
cites work: Q4228446
cites work: Q4038737
cites work: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
cites work: Q4223149
cites work: On Computations with Dense Structured Matrices
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Q4226935
cites work: Block solution of sparse linear systems over GF (q)
cites work: Solving sparse linear equations over finite fields
cites work: Q3851616
Recommended article: Preconditioners for singular black box matrices
Recommended article: Black box linear algebra
Recommended article: Preconditioning linear systems via matrix function evaluation
Recommended article: Matrix algebras in optimal preconditioning
Recommended article: Explicit preconditioning of systems of linear algebraic equations with dense matrices
Recommended article: A unifying approach to abstract matrix algebra preconditioning
Recommended article: Optimal preconditioners for functions of matrices
Recommended article: Q3558545
Recommended article: Q4309414
Recommended article: Efficient Preconditioning of Sequences of Nonsymmetric Linear Systems
description: scientific article; zbMATH DE number 1741658