Black box methods for least squares problems

ABSTRACT

We present algorithms to construct an efficient black box for the pseudoinverse, A^t, of a black box matrix A. This in also known as the Moore-Penrose inverse of A. For the system Ax = b over a subfield of the complex numbers: the vector x = A^tb is the least squares solution having the least norm. When we say that A is a black box matrix we mean simply that methods are given to compute the matrix-vector products Au and u^TA, for vectors u and vectors v of compatible length. No other assumptions are made about the structure or representation of the matrix.

The entries may be integers or rational numbers or elements of a finite field. For the integer or rational case the method uses homomorphic images, and is based on an algorithm capable of computing the black box for the pseudoinverse, when it exists, over an arbitrary field. We discuss the asymptotic costs and some variants that are likely to be useful in practice.

Over a finite field the solution, x = A^tb, is uniquely defined when it exists. The ability to produce this particular solution is a useful addition to the range of ways solution to singular linear systems may be offered in the black box model.

REFERENCES

• 1: BEN-ISRAEL, A., AND GREVILLE, T. Generalized Inverses: Theory and Applications. Wiley, New York, 1974.
• 2: CHEN, L., EBERLY, W., KALTOFEN, E., SAUNDERS, B. D., TURNER, W. J., AND VILLARD, g . Efficient matrix preconditioners for black box linear algebra, Jan. 2000. Manuscript submitted for publication.
• 3: James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 4: DIXON, J. D. Exact solution of linear equations using p-adic expansions. Numerische Mathematik 40 (1982), 137-141.
• 5: DUMAS, J.-G. Algorithmes parallles eeaces pour le calcul formel : Algbre lingaire creuse et extensions algdbriques. PhD thesis, Universit6 Joseph Fourier et Ecole Nationale Sup6rieure d'Informatique et de Math6matiques Appliqu6es de Grenoble, 2000.
• 6: Jean-Guillaume Dumas , B. David Saunders , Gilles Villard, Integer Smith form via the valence: experience with large sparse matrices from homology, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.95-105, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345590]
• 7: Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258776]
• 8: M. Giesbrecht , A. Lobo , B. D. Saunders, Certifying inconsistency of sparse linear systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.113-119, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281591]
• 9: Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
• 10: PEARL, M. H. Generalized inverses of matrices with entries taken from an arbitrary field. Linear Algebra and its Applications 1 (1968), 571-587.
• 11: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

General Terms:
Algorithms, Experimentation, Performance, Verification