An algorithm to compute a sparse basis of the null space
Let A be a real \(m\times 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\times 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 mainframe computer with an FPS-164 attached array processor at the Triangle Universities Computing Center near Raleigh, N. C.. 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, ill-conditioned problems.
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 3949599 (Why is no real title available?)
- scientific article; zbMATH DE number 883145 (Why is no real title available?)
- Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition
- Minimum norm solutions to linear elastic analysis problems
- Numerical Solution of Navier–Stokes Problems by the Dual Variable Method
- On computational procedures for the force method
- Solution of Large-Scale Sparse Least Squares Problems Using Auxiliary Storage
- Solution of sparse linear least squares problems using Givens rotations
- Sparse Orthogonal Schemes for Structural Optimization Using the Force Method
- Algorithms and experiments for structural mechanics on high-performance architectures
- Sparse null basis computations in structural optimization
- On the computation of multi-dimensional solution manifolds of parametrized equations
- Construction of null bases for the divergence operator associated with incompressible Navier-Stokes equations
- A constrained least-squares approach to the rapid reanalysis of structures
- A direct flexibility method
- Null space algorithm and spanning trees in solving Darcy's equation
- Conference celebrating the 60th birthday of Robert J. Plemmons. Papers from the conference, Winston-Salem, NC, USA, January 1999
- Dedication to Robert J. Plemmons
- A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time
- The derivation of minimal support basis functions for the discrete divergence operator
- An efficient algorithm for sparse null space basis problem using ABS methods
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- A null-space approach for large-scale symmetric saddle point systems with a small and non zero \((2, 2)\) block
- Sparse self-stress matrices for the finite element force method
- Continuous numerical solutions for a base of null space of matrix functions whose ranks are not full
- A Symbolic Approach to Compute a Null-Space Basis in the Projection Method
- Nested Dissection for Sparse Nullspace Bases
- A note on the computation of an orthonormal basis for the null space of a matrix
- Substructuring Methods for Computing the Nullspace of Equilibrium Matrices
- On the Computation of Null Spaces of Sparse Rectangular Matrices
- Properties of a representation of a basis for the null space
- scientific article; zbMATH DE number 3949599 (Why is no real title available?)
- The Dual Variable Method for the Solution of Compressible Fluid Flow Problems
- The Null Space Problem I. Complexity
- A Parallel Block Iterative Scheme Applied to Computations in Structural Analysis
- Computing a Sparse Basis for the Null Space
- The Null Space Problem II. Algorithms
- An application of the Dulmage-Mendelsohn decomposition to sparse null space bases of full row rank matrices
- Computing minimal nullspace bases
- A fast randomized algorithm for computing an approximate null space
- Cardinality minimization, constraints, and regularization: a survey
- Sequential hierarchical least-squares programming for prioritized non-linear optimal control
- MANPAK: A set of algorithms for computations on implicitly defined manifolds
- Iterative solution of Navier-Stokes dual variable difference equations
- The dual variable method for solving fluid flow difference equations on Delaunay triangulations
- Order-reducing conjugate gradients versus block AOR for constrained least-squares problems
- Combinatorial algorithms for computing column space bases that have sparse inverses
- Canonical bases in linear programming
- Block computation and representation of a sparse nullspace basis of a rectangular matrix
This page was built for publication: An algorithm to compute a sparse basis of the null space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799342)
