Efficient Matrix Preconditioners for Black Box Linear Algebra

Lin Chen (1) , W. Eberly (1) , Erich Kaltofen (1) , B.D. Saunders (1) , W.J. Turner (1) , Gilles Villard (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

The main idea of the ``black box'' approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the desired result. Here, good preconditioners will be used to ensure geometrical / algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We include new conditioners, new analyses of preconditioner performance, and results on the relations among preconditioning problems and with linear algebra problems. Thus improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields.

L'idée principale de l’approche à base de boîtes noires en algèbre linéaire exacte est de ramener la réquisition de problèmes matriciels à des calculs de polynômes minimaux. Dans le plupart des cas, un préconditionnement s'avère nécessaire pour obtenir le résultat désiré. nous parlerons de "bons" préconditionnements quand il s'agira d'assurer des propriétés géométriques et algébriques sur les matrices plutôt que des qualités numériques, donc sans relation avec un nombre de conditionnement. dans ce rapport nous passons en revue divers problèmes pour lesquels on utilise un préconditionnement (algébrique), proposons une classification des différents problèmes de préconditionnement et étudions plusieurs solutions. En particulier, nous envisageons de nouveaux préconditionnements, de nouvelles analyses de leurs performances et des relations pouvant être définies entre eux en rapport avec les questions d'algèbre linéaire qu'ils résolvent. Des améliorations sont donc obtenues quant à l’efficacité et l’applicabilité des préconditionnements. Ces résultats se concentrent sur des matrices à coefficients dans des corps finis mais ils s'appliquent dans le cas de corps commutatifs quelconques

Mots clés: Black Box Matrix; Exact Arithmetic; Finite Fields; Linear Algebra; Linear Systems; Preconditioner; Randomized Algorithms; Rank; Sparse Matrix

Mots clés: Arithmétique exacte; Corps finis; Systèmes linéaires; Rang; Préconditionnement; Algèbre linéaire; Algorithmes probabilistes; Matrice boîte noire; Matrice creuse

Domaines: Informatique [cs]

Lin Chen, W. Eberly, Erich Kaltofen, B.D. Saunders, W.J. Turner, et al.. Efficient Matrix Preconditioners for Black Box Linear Algebra. [Research Report] LIP RR-2001-05, Laboratoire de l'informatique du parallélisme. 2001, 2+18p. ⟨hal-02101893⟩