Hybrid Algorithms for Rank of Sparse Matrices

Creative Commons License

Duran A., Saunders D., Wan Z.

SIAM Int. Conference on Applied Linear Algebra (SIAM-LA), Virginia, United States Of America, 16 - 19 July 2003, pp.1-12

  • Publication Type: Conference Paper / Full Text
  • City: Virginia
  • Country: United States Of America
  • Page Numbers: pp.1-12
  • Istanbul Technical University Affiliated: No


In this study we compare two distinct methods for solving basic linear algebra problems for sparse matrices over the integers and over finite fields. Here we focus on the problem of rank. One method is GSLU, an adaptation of the SuperLU method and it is fundamentally Gaussian elimination. The second method, called here BB for "black box", is a variant of Wiedemann's algorithm and is a Krylov space method. The methods may be applied to other problems such as determinant, system solving, and Smith normal form.  Our experiments provide a basis for hybrid algorithms and we present and evaluate two hybrids for use in our library LinBox, which may be found on the web at linalg.org.

Given the uncertainty, one solution is to race the two methods, stopping the slower one when the faster one finishes. When two processors are available, the faster time is achieved. When only one (timesharing) processor is available, racing still runs in no more than twice the faster time. We implemented a general purpose racing utility and found negligible overhead.