A parallel block algorithm for exact triangularization of rectangular matrices

ABSTRACT

A new block algorithm for triangularization of regular or singular matrices with dimension m × n is proposed. Taking benefit of fast block multiplication algorithms, it achieves the best known sequential complexity &Ogr;(m^w-1n) for any sizes and any rank. Moreover, the block strategy enables to improve locality with respect to previous algorithms as exhibited by practical performances.

REFERENCES

• 1: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 2: Fred G. Gustavson , André Henriksson , Isak Jonsson , Bo Kågström , Per Ling, Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms, Proceedings of the 4th International Workshop on Applied Parallel Computing, Large Scale Scientific and Industrial Problems, p.195-206, June 14-17, 1998
• 3: O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms, 3(1):45-56, Mar. 1982.
• 4: K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, v.7 n.1, p.101-104, Jan. 1987 [doi>10.1007/BF02579205]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

General Terms:
Algorithms, Measurement, Performance, Theory