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 and 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, 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

show all references

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

[1]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and 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 and 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 and Continuous Dynamical Systems, 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]

Doston Jumaniyozov, Ivan Kaygorodov, Abror Khudoyberdiyev. The algebraic classification of nilpotent commutative algebras. Electronic Research Archive, 2021, 29 (6) : 3909-3993. doi: 10.3934/era.2021068
[7]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems and Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[8]

Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems and Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123
[9]

Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems and Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016
[10]

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

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 and Continuous Dynamical Systems - B, 2019, 24 (10) : 5569-5596. doi: 10.3934/dcdsb.2019072
[12]

Isaac A. García, Douglas S. Shafer. Cyclicity of a class of polynomial nilpotent center singularities. Discrete and Continuous Dynamical Systems, 2016, 36 (5) : 2497-2520. doi: 10.3934/dcds.2016.36.2497
[13]

Mark Pollicott. Ergodicity of stable manifolds for nilpotent extensions of Anosov flows. Discrete and Continuous Dynamical Systems, 2002, 8 (3) : 599-604. doi: 10.3934/dcds.2002.8.599
[14]

Clara Cufí-Cabré, Ernest Fontich. Differentiable invariant manifolds of nilpotent parabolic points. Discrete and Continuous Dynamical Systems, 2021, 41 (10) : 4667-4704. doi: 10.3934/dcds.2021053
[15]

Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems and Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123
[16]

Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems and Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263
[17]

Xiaodong Liu. The factorization method for scatterers with different physical properties. Discrete and Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563
[18]

Katrin Gelfert. Lower bounds for the topological entropy. Discrete and Continuous Dynamical Systems, 2005, 12 (3) : 555-565. doi: 10.3934/dcds.2005.12.555
[19]

Ariel Salort. Lower bounds for Orlicz eigenvalues. Discrete and Continuous Dynamical Systems, 2022, 42 (3) : 1415-1434. doi: 10.3934/dcds.2021158
[20]

P. De Maesschalck. Gevrey normal forms for nilpotent contact points of order two. Discrete and Continuous Dynamical Systems, 2014, 34 (2) : 677-688. doi: 10.3934/dcds.2014.34.677

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy