Preconditioners for singular black box matrices

ABSTRACT

This paper develops preconditioners for singular black box matrix problems. We introduce networks of arbitrary radix switches for matrices of any square dimension, and we show random full Toeplitz matrices are adequate switches for these networks. We also show a random full Toeplitz matrix to satisfy all requirements of the Kaltofen-Saunders black box matrix rank algorithm without requiring a diagonal multiplier.

REFERENCES

• 1: Beneš, V. E. Permutation groups, complexes, and rearrangeable connecting networks. Bell System Tech. J. 43 (1964), 1641--1656.
• 2: Chen, L., Eberly, W., Kaltofen, E., Saunders, B. D., Turner, W. J., and Villard, G. Efficient matrix preconditioners for black box linear algebra. Linear Algebra Appl. 343-344 (Mar. 2002), 119--146. Special issue on Infinite Systems of Linear Equations Finitely Specified, edited by P. Dewilde, V. Olshevsky and A. H. Sayed.
• 3: Cox, D., Little, J., and O'Shea, D. Ideals, Varieties, and Algorithms: An Introduction to Computational Geometry and Commutative Algebra. Springer Verlag, Heidelberg, Germany, 1996.
• 4: 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]
• 5: Gantmacher, F. R. Matrix Theory, vol. I. AMS Chelsea Pub., Providence, 1977.
• 6: Hoffman, K., and Kunze, R. Linear Algebra, 2nd ed. Prentice Hall, Upper Saddle River, NJ, 1971.
• 7: E. Kaltofen , A. Lobo, On rank properties of Toeplitz matrices over finite fields, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.241-249, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237081]
• 8: 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
• 9: Parker, D. S. Random butterfly transformations with applications in computational linear algebra. Technical Report CSD-950023, UCLA, 1995.
• 10: William Jonathan Turner , Erich Kaltofen, Black box linear algebra with the linbox library, 2002
• 11: Turner, W. J. Determinantal divisors and matrix preconditioners. Submitted to J. Symbolic Comput., June 2003.
• 12: 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]
• 13: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
Toeplitz matrix, Wiedemann method, black box linear algebra, rank preconditioner, singular linear system, switching network