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]

Rim Bourguiba, Rosana Rodríguez-López. Existence results for fractional differential equations in presence of upper and lower solutions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1723-1747. doi: 10.3934/dcdsb.2020180
[2]

Alessandro Fonda, Rodica Toader. A dynamical approach to lower and upper solutions for planar systems "To the memory of Massimo Tarallo". Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021012
[3]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[4]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[5]

Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123
[6]

Alex P. Farrell, Horst R. Thieme. Predator – Prey/Host – Parasite: A fragile ecoepidemic system under homogeneous infection incidence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 217-267. doi: 10.3934/dcdsb.2020328
[7]

Xin Zhao, Tao Feng, Liang Wang, Zhipeng Qiu. Threshold dynamics and sensitivity analysis of a stochastic semi-Markov switched SIRS epidemic model with nonlinear incidence and vaccination. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021010
[8]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269
[9]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[10]

S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020435
[11]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375
[12]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[13]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356
[14]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076
[15]

Yueh-Cheng Kuo, Huan-Chang Cheng, Jhih-You Syu, Shih-Feng Shieh. On the nearest stable $ 2\times 2 $ matrix, dedicated to Prof. Sze-Bi Hsu in appreciation of his inspiring ideas. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020358

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences