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

研究成果: Article査読

44 被引用数 (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.

ジャーナルNumerische Mathematik
出版ステータスPublished - 1985 12月

ASJC Scopus subject areas

  • 計算数学
  • 応用数学


「An algorithm to compute a sparse basis of the null space」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。