Sparse inverse incidence matrices   for Schilders' factorization applied    to resistor network modeling

Sangye  Lungten; Wil H. A. Schilders; Joseph M. L.  Maubach

doi:10.3934/naco.2014.4.227

Article Contents

2014, Volume 4, Issue 3: 227-239. Doi: 10.3934/naco.2014.4.227

This issue Previous Article Two-step methods for image zooming using duality strategies Next Article Stochastic programming approach for energy management in electric microgrids

Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling

1.
Center for Analysis, Scientific Computing and Applications, Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB, Eindhoven

Received: November 30, 2013

Revised: July 31, 2014

Published: August 2014

Abstract Related Papers Cited by

Abstract

Schilders' factorization can be used as a basis for preconditioning indefinite linear systems which arise in many problems like least-squares, saddle-point and electronic circuit simulations. Here we consider its application to resistor network modeling. In that case the sparsity of the matrix blocks in Schilders' factorization depends on the sparsity of the inverse of a permuted incidence matrix. We introduce three different possible permutations and determine which permutation leads to the sparsest inverse of the incidence matrix. Permutation techniques are based on types of sub-digraphs of the network of an incidence matrix.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, 2nd edition, Springer-Verlag, New York, 2012.doi: 10.1007/978-1-4614-4529-6.
[2]	R. B. Bapat, Graphs and Matrices, Hindustan Book Agency, New Delhi, Springer-Verlag, London and Dordrecht, Heidelberg, New York, 2010.doi: 10.1007/978-1-84882-981-7.
[3]	G. Chartrand and L. Lesniak, Graphs and Digraphs, 3rd edition, Chapman and Hall/CRC Press, Boca Raton, London, 1996.
[4]	Z. Lijang, A matrix solution to Hamiltonian path of any graph, International conference on intelligent computing and cognitive informatics, IEEE 2010.
[5]	J. Rommes and W. H. A. Schilders, Efficient methods for large resistor networks, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 29 (2010), 28-39.
[6]	Y. Saad, Preconditioning techniques for nonsymetric and indefinite linear systems, Journal of Computational and Applied Mathematics, 24 (1988), 89-105.doi: 10.1016/0377-0427(88)90345-7.
[7]	W. H. A. Schilders, Solution of indefinite linear systems using an LQ decomosition for the linear constraints, Linear Algebra and Applications, 431 (2009), 381-395.doi: 10.1016/j.laa.2009.02.036.
[8]	R. Vandebril, M. V. Barel and N. Mastronardi, Matrix Computations and Semiseparable Matrices, The Johns Hopkins University Press, Baltimore, Marylan