Black Box Linear Algebra
Problems concerned with the solution of systems of linear equations are fundamental — they arise, in more-or-less hidden form, in a wide variety of areas of science and engineering. Efficient algorithms to solve linear systems are well known and widely used.
The systems of equations that arise in practice often have additional structural properties that allow them to be solved more efficiently than is possible in the general case. Thus, the study of sparse and various kinds of structured systems are research areas in their own right. There is frequently a special-purpose algorithm that can be used to solve a structured system — assuming, of course, that you know precisely what structure the system has.
One might also hope to look for algorithms that are more flexible than these dedicated algorithms. Ideally, such algorithms would automatically take advantage of special properties of systems, in order to reduce the cost of solving them.
"Black box linear algebra" concerns one attempt to find such algorithms. This is a study of algorithms that solve matrix problems assuming that the input matrix A is given only by an oracle or "black box" that can be used to compute the product of A and a given vector x. If you wish to solve a problem (using a "black box" method) involving a matrix A — say, to solve a linear system having A as the coefficient matrix — then you would do so by using a small number of calls to this black box and performing a limited number of additional computations — without trying to access the matrix A in any other way.
The Linbox project is a research project with the goal of developing a system for solving linear systems in an efficient way, particular, using black-box techniques. Much of my research in recent years as been a part of the work of this project.
Black box algorithms usually work by treating matrices as operators on vector spaces. There exist various "normal forms" for matrices that provide information about how the matrices function as operators and — perhaps, not surprisingly — the study of black box matrix computations and the study of matrix normal forms seem closely linked. Recent work by the Linbox group has included new algorithms for the computation of various matrix normal forms.
L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner,
and G. Villard
Efficient Matrix Preconditioners for Black Box Linear
Algebra
Linear Algebra and Its Applications 343–344
(2002); pp. 119–146
One of the more recent publications by the Linbox research group. This also includes references to quite a bit of the recent work on black box linear algebra.
J. von zur Gathen and J. Gerhard
Modern Computer Algebra
Cambridge University Press, 1999
Chapter 12 ("Fast Linear Algebra") includes a short introduction to Black Box Linear Algebra, along with a presentation of Wiedemann's algorithm.
R. Lambert
Computational Aspects of Discrete Logarithms
PhD Thesis, Univeristy of Waterloo, 1986
While Wiedemann's algorithm was the first algorithm to be recognized as a "black box" algorithm, it was not the first such algorithm to exist or be used: Both the Lanczos algorithm and the conjugate-gradient algorithm are algorithms that have been known and used for decades, and both of these can be considered to be black box algorithms, as well.
Indeed — as R. Lambert explains, in his thesis — Wiedemann's algorithm, the Lanczos algorithm, and the conjugate-gradient algorithm can all be considered to be variations of the same method. The thesis is very useful if you wish to understand this method better, and see how these three algorithms are related.
The Linbox project's home page includes the most recent version of the LinBox software that is available for distribution.
It also includes links the home pages of researchers in the group. You can find more up-to-date references for the work of this group there.
D. H. Wiedemann
Solving Sparse Linear Equations over Finite Fields
IEEE Transactions on Information Theory IT-32
(1986), pp. 54–62
Although it is not identified as such in this paper, Wiedemann's algorithm was the first algorithm to be identified as a "black box" algorithm in linear algebra. This paper includes both a presentation of this algorithm, and its analysis, and a variety of applications and extensions. It is definitely worth study by anyone wishing to work in this area.
Randomized Lanczos Algorithms
W. Eberly and E. Kaltofen
On Randomized Lanczos Algorithms
Proceedings, 1997 International Symposium on Symbolic and
Algebraic Computation
Maui, Hawaii, 1997; pp. 176–83
Longer Version, Including Proofs:
[ Postscript ]
[ PDF ]
Inspired by a consideration of randomizations of the Lanczos algorithms that were used in practice for computations over large fields, a sequence of (somewhat modified) randomizations were presented and analyzed.
Matrix Preconditioning
L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner,
and G. Villard
Efficient Matrix Preconditioners for Black Box Linear
Algebra
Linear Algebra and Its Applications 343–344
(2002); pp. 119–146
Available online at
ScienceDirect.
It is frequently useful, when considering black box matrix computations, to "precondition" the given matrix by applying a randomly chosen sparse or structured matrix, in order to ensure that the resulting matrix is (in some useful sense) well-behaved with high probability. This paper presents a number of computational problems for which black-box algorithms have currently been developed, along with matrix properties that are required in order to establish correctness of the algorithms, and matrix preconditioners that ensure these properties with reasonable probability.
Early Termination over Small Fields
W. Eberly
Early Termination over Small Fields
© ACM, 2003
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for distribution. The definitive version was publshed in Proceedings, 2003 International Symposium on Symbolic and Algebraic Computation, Philadelphia, Pennsylvania, 2003; pp. 80–87, http://doi.acm.org/10.1145/860854.860882.
Longer Version, Including Proofs: [ Postscript ] [ PDF ]
Motivated by experimental work of Austin Lobo, this work analyzes the likelihood of long lookahead blocks when a randomized Lanczos algorithm is applied to solve a system of linear equations over a small finite field, as well as the likelihood of long sequences of zero discrepancies when the Berlekamp-Massey algorithm is used as part of an application of Wiedemann's algorithm to solve the same problem. A modified version of the Lanczos algorithm is proposed on the basis of this analysis.
Reliable Krylov-Based Algorithms for Matrix Null Space and Rank
W. Eberly
Reliable Krylov-Based Algorithms for Matrix Null Space
and Rank
© ACM, 2004
This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for distribution. The definitive version was published in Proceedings, 2004 International Symposium on Symbolic and Algebraic Computation, Santander, Spain, 2004; pp. 127–134, http://doi.acm.org/10.1145/1005285.1005305.
Longer Version, Including Proofs: [ Postscript ] [ PDF ]
A simple block-Lanczos algorithm for computations over large finite fields and an algorithm that computes a partial Frobenius decomposition over small finite fields are each described, along with their uses to compute the ranks of matrices and sample from null spaces.
It is likely that the most useful results concern the use of (essentially) Wiedemann's sparse preconditioner to bound the number of invariant factors of a matrix without changing its rank: It currently seems likely that this can be used together with block Lanczos algorithms, now being developed and analyzed, to sample reliably from the null space of an arbitrary matrix over a small finite field.
Analysis of Block Algorithms
W. Eberly and B. Hovinen
Bounding the Nullities of Random Block Hankel Matrices:
An Alternative Approach
Department of Computer Science, University of Calgary
Technical Report 2005–779–10
May, 2005
This is one of two reports (the other to be presented at ISSAC in 2005) that provides bounds on the probabilities that various block Hankel matrices are rank deficient. These are potentially of use to analyze block Lanczos algorithms as well as block Wiedemann algorithms incorporating early termination when these are applied to systems over small finite fields.
Computations of Frobenius Normal Forms
W. Eberly
Black Box Frobenius Decompositions over Small Fields
Extended Abstract
Proceedings, 2000 International Symposium on Symbolic
and Algebraic Computation
St. Andrews, Scotland, 2000; pp. 106–113
W. Eberly
Asymptotically Efficient Algorithms for the Frobenius Form
Department of Computer Science, University of Calgary
Technical Report, 2000
Technical Report:
[ Postscript ]
[ PDF ]
Techniques that had been applied by Wiedemenn and Lanczos to solve systems of linear equations were combined in order to produce an algorithm to compute the Frobenius normal form of a matrix over a field. The extended abstract, presented at ISSAC, describes a "black box" version of the algorithm for computation over small finite fields. The technical report also includes an asymptotically efficient algorithm (using fast matrix multiplication) that slightly improved the known bound on the complexity of this computation
Determinant and Smith Normal Form of an Integer Matrix
W. Eberly, M. Giesbrecht, and G. Villard
On Computing the Determinant and Smith Form of an Integer
Matrix
Proceedings, 41st Annual Symposium on Foundations of
Computer Science
Redondo Beach, California, 2000; pp. 675–685
Techniques that had been developed by Gilles Villard, to produce a black box algorithm to compute the Frobenius normal form of a matrix over a field, were applied here to integer computations.
This established a new — and, very short-lived — upper bound on the complexity of the problem of computing the determinant of an integer determinant, but on the other hand, it does seem to have renewed interest the problem: The techniques used here were almost immediately combined with those used in other algorithms to push the bound still lower.
This page was most recently changed on Saturday, September 10, 2005 by Wayne Eberly.
