American Institute of Mathematical Sciences

Advanced
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

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]

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
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[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]

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
[15]

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
[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]

Montserrat Corbera, Claudia Valls. Reversible polynomial Hamiltonian systems of degree 3 with nilpotent saddles. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020225
[20]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (43)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences