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

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

2014, 4(3): 227-239. doi: 10.3934/naco.2014.4.227

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

Sangye Lungten ^1, , Wil H. A. Schilders ^1, and Joseph M. L. Maubach ^1,

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

Received December 2013 Revised August 2014 Published September 2014

Abstract
Related Papers

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: incidence matrix, Schilders' factorization, lower trapezoidal, nilpotent., digraph.

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

Citation: Sangye Lungten, Wil H. A. Schilders, Joseph M. L. Maubach. Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 227-239. doi: 10.3934/naco.2014.4.227

References:

[1]	R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory,, 2nd edition, (2012). doi: 10.1007/978-1-4614-4529-6. Google Scholar
[2]	R. B. Bapat, Graphs and Matrices,, Hindustan Book Agency, (2010). doi: 10.1007/978-1-84882-981-7. Google Scholar
[3]	G. Chartrand and L. Lesniak, Graphs and Digraphs,, 3rd edition, (1996). Google Scholar
[4]	Z. Lijang, A matrix solution to Hamiltonian path of any graph,, International conference on intelligent computing and cognitive informatics, (2010). Google Scholar
[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. Google Scholar
[6]	Y. Saad, Preconditioning techniques for nonsymetric and indefinite linear systems,, Journal of Computational and Applied Mathematics, 24 (1988), 89. doi: 10.1016/0377-0427(88)90345-7. Google Scholar
[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. doi: 10.1016/j.laa.2009.02.036. Google Scholar
[8]	R. Vandebril, M. V. Barel and N. Mastronardi, Matrix Computations and Semiseparable Matrices,, The Johns Hopkins University Press, (). Google Scholar

show all references

References:

[1]	R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory,, 2nd edition, (2012). doi: 10.1007/978-1-4614-4529-6. Google Scholar
[2]	R. B. Bapat, Graphs and Matrices,, Hindustan Book Agency, (2010). doi: 10.1007/978-1-84882-981-7. Google Scholar
[3]	G. Chartrand and L. Lesniak, Graphs and Digraphs,, 3rd edition, (1996). Google Scholar
[4]	Z. Lijang, A matrix solution to Hamiltonian path of any graph,, International conference on intelligent computing and cognitive informatics, (2010). Google Scholar
[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. Google Scholar
[6]	Y. Saad, Preconditioning techniques for nonsymetric and indefinite linear systems,, Journal of Computational and Applied Mathematics, 24 (1988), 89. doi: 10.1016/0377-0427(88)90345-7. Google Scholar
[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. doi: 10.1016/j.laa.2009.02.036. Google Scholar
[8]	R. Vandebril, M. V. Barel and N. Mastronardi, Matrix Computations and Semiseparable Matrices,, The Johns Hopkins University Press, (). Google Scholar

[1]	Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025
[2]	Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601
[3]	Daniel Genin. Research announcement: Boundedness of orbits for trapezoidal outer billiards. Electronic Research Announcements, 2008, 15: 71-78. doi: 10.3934/era.2008.15.71
[4]	Percy Fernández-Sánchez, Jorge Mozo-Fernández, Hernán Neciosup. Dicritical nilpotent holomorphic foliations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (7) : 3223-3237. doi: 10.3934/dcds.2018140
[5]	Tracy L. Payne. Anosov automorphisms of nilpotent Lie algebras. Journal of Modern Dynamics, 2009, 3 (1) : 121-158. doi: 10.3934/jmd.2009.3.121
[6]	Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]	Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems & Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016
[8]	Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems & Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123
[9]	Yao Lu, Rui Zhang, Dongdai Lin. Improved bounds for the implicit factorization problem. Advances in Mathematics of Communications, 2013, 7 (3) : 243-251. doi: 10.3934/amc.2013.7.243
[10]	Isaac A. García, Douglas S. Shafer. Cyclicity of a class of polynomial nilpotent center singularities. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2497-2520. doi: 10.3934/dcds.2016.36.2497
[11]	Mark Pollicott. Ergodicity of stable manifolds for nilpotent extensions of Anosov flows. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 599-604. doi: 10.3934/dcds.2002.8.599
[12]	Jiu-Gang Dong, Seung-Yeal Ha, Doheon Kim. Interplay of time-delay and velocity alignment in the Cucker-Smale model on a general digraph. Discrete & Continuous Dynamical Systems - B, 2019, 24 (10) : 5569-5596. doi: 10.3934/dcdsb.2019072
[13]	Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems & Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123
[14]	Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems & Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263
[15]	Xiaodong Liu. The factorization method for scatterers with different physical properties. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563
[16]	P. De Maesschalck. Gevrey normal forms for nilpotent contact points of order two. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 677-688. doi: 10.3934/dcds.2014.34.677
[17]	Luca Capogna. Optimal regularity for quasilinear equations in stratified nilpotent Lie groups and applications. Electronic Research Announcements, 1996, 2: 60-68.
[18]	Antonio Algaba, María Díaz, Cristóbal García, Jaume Giné. Analytic integrability around a nilpotent singularity: The non-generic case. Communications on Pure & Applied Analysis, 2020, 19 (1) : 407-423. doi: 10.3934/cpaa.2020021
[19]	Katrin Gelfert. Lower bounds for the topological entropy. Discrete & Continuous Dynamical Systems - A, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555
[20]	Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009

Impact Factor:

American Institute of Mathematical Sciences