An efficient algorithm for sparse null space basis problem using ABS methods

DOI10.1007/s11075-012-9599-1zbMath1262.65055MaRDI QIDQ1944750

Nezam Mahdavi-Amiri, Mostafa Khorramizadeh

Publication date: 27 March 2013

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11075-012-9599-1

zbMATH Keywords

linear programming; numerical results; sparse matrix; null space basis; extended ABS algorithm; Markowitz criterion

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

65K05: Numerical mathematical programming methods

90C05: Linear programming

Related Items

Identification of unidentified equality constraints for integer programming problems, General solution of full row rank linear systems of equations using a new compression ABS model

Uses Software

• Matlab
• UMFPACK
• SPARSE-QR
• NETLIB LP Test Set
• CSparse

Cites Work

• Unnamed Item
• ABS methods for continuous and integer linear equations and optimization
• A class of direct methods for linear systems
• An algorithm to compute a sparse basis of the null space
• Block computation and representation of a sparse nullspace basis of a rectangular matrix
• Separators and structure prediction in sparse orthogonal factorization
• ABS methods and ABSPACK for linear systems and optimization: A review
• Maintaining LU factors of a general sparse matrix
• The Elimination form of the Inverse and its Application to Linear Programming
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Nested Dissection for Sparse Nullspace Bases
• On computational procedures for the force method
• Direct Methods for Sparse Linear Systems
• Substructuring Methods for Computing the Nullspace of Equilibrium Matrices
• Estimation of sparse hessian matrices and graph coloring problems
• Sparse Orthogonal Schemes for Structural Optimization Using the Force Method
• Numerical Solution of Navier–Stokes Problems by the Dual Variable Method
• The Null Space Problem I. Complexity
• Computing a Sparse Basis for the Null Space
• The Null Space Problem II. Algorithms
• A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
• Sparse QR factorization in MATLAB
• A primal null-space affine-scaling method
• Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
• Algorithm 832