Nested Dissection for Sparse Nullspace Bases
Authors:
- Julio M. SternJulio M. Stern
- Stephen A. VavasisSVStephen A. Vavasis
- 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
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 9 references indexed in Scilit:
- Simulated Annealing with a Temperature Dependent Penalty FunctionINFORMS Journal on Computing, 1992
- Planar separators and the Euclidean normLecture Notes in Computer Science, 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