Nested Dissection for Sparse Nullspace Bases
- 1 July 1993
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 14 (3) , 766-775
- https://doi.org/10.1137/0614054
Abstract
The authors propose a nested dissection approach to finding a fundamental cycle basis in a planar graph. The cycle basis corresponds to a fundamental nullspace basis of the adjacency matrix. This problem is meant to model sparse nullspace basis computations occurring in a variety of settings. An $O( n^{3/2} )$ bound is achieved on the nullspace basis size (i.e., the number of nonzero entries in the basis), and $O( n\log n )$ an bound on the size in the special case of grid graphs.
Keywords
This publication has 10 references indexed in Scilit:
- A unified geometric approach to graph separatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Simulated Annealing with a Temperature Dependent Penalty FunctionINFORMS Journal on Computing, 1992
- Planar separators and the Euclidean normPublished by Springer Nature ,1990
- Substructuring Methods for Computing the Nullspace of Equilibrium MatricesSIAM Journal on Matrix Analysis and Applications, 1990
- A Framework for Equilibrium EquationsSIAM Review, 1988
- The Null Space Problem II. AlgorithmsSIAM Journal on Algebraic Discrete Methods, 1987
- Computing a Sparse Basis for the Null SpaceSIAM Journal on Algebraic Discrete Methods, 1987
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- On computational procedures for the force methodInternational Journal for Numerical Methods in Engineering, 1982
- Nested Dissection of a Regular Finite Element MeshSIAM Journal on Numerical Analysis, 1973