An algorithm to compute a sparse basis of the null space

M. W. Berry, M. T. Heath, I. Kaneko, M. Lawo, R. J. Plemmons, R. C. Ward

Research output: Contribution to journalArticlepeer-review

44 Citations (Scopus)


Let A be a real m×n matrix with full row rank m. In many algorithms in engineering and science, such as the force method in structural analysis, the dual variable method for the Navier-Stokes equations or more generally null space methods in quadratic programming, it is necessary to compute a basis matrix B for the null space of A. Here B is n×r, r=n-m, of rank r, with AB=0. In many instances A is large and sparse and often banded. The purpose of this paper is to describe and test a variation of a method originally suggested by Topcu and called the turnback algorithm for computing a banded basis matrix B. Two implementations of the algorithm are given, one using Gaussian elimination and the other using orthogonal factorization by Givens rotations. The FORTRAN software was executed on an IBM 3081 computer with an FPS-164 attached array processor at the Triangle Universities Computing Center and on a CYBER 205 vector computer. Test results on a variety of structural analysis problems including two- and three-dimensional frames, plane stress, plate bending and mixed finite element problems are discussed. These results indicate that both implementations of the algorithm yielded a well-conditioned, banded, basis matrix B when A is well-conditioned. However, the orthogonal implementation yielded a better conditioned B for large, illconditioned problems.

Original languageEnglish
Pages (from-to)483-504
Number of pages22
JournalNumerische Mathematik
Issue number4
Publication statusPublished - 1985 Dec


  • Subject Classifications: AMS(MOS), 65F30, CR: G1.3

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'An algorithm to compute a sparse basis of the null space'. Together they form a unique fingerprint.

Cite this