×

Arnoldi algorithms with structured orthogonalization. (English) Zbl 1520.65028

The authors present a stability preserved Arnoldi algorithm with the aim of studying large-scale power delivery networks (PDNs), whose time domain simulation is chosen to be solved by semi-explicit differential algebraic equations (DAEs). A matrix exponential based integration method is used since it is not bounded by the Dalquist stability barrier, unlike the traditional linear multistep methods. Solutions \(x(t)\) to PDNs can be expressed as a sum of \(x_{R}(t)\) and \(x_{N}(t)\), one in the range of the system operator and the other in its null space. Then, \(\ x_{R}(t)\) can be computed by a shift-and-invert Krylov subspace method, whereas \(x_{N}(t)\) can be computed by algebraic equations. A complete Arnoldi algorithm with explicit structured orthogonalization and implicit regularization is reported. Convergence analysis is studied in details and error bounds are provided. At last, simulations on RLC networks are provided to enlighten the effectiveness of the presented method.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
34A09 Implicit ordinary differential equations, differential-algebraic equations
65L80 Numerical methods for differential-algebraic equations

Software:

SPICE; mftoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B. Beckermann and L. Reichel, Error estimates and evaluation of matrix functions via the Faber transform, SIAM J. Numer. Anal., 47 (2009), pp. 3849-3883, https://doi.org/10.1137/080741744. · Zbl 1204.65041
[2] C. A. Berger and J. G. Stampfli, Mapping theorems for the numerical range, Amer. J. Math., 89 (1967), pp. 1047-1055. · Zbl 0164.16602
[3] M. A. Botchev, V. Grimm, and M. Hochbruck, Residual, restarting, and Richardson iteration for the matrix exponential, SIAM J. Sci. Comput., 35 (2013), pp. A1376-A1397, https://doi.org/10.1137/110820191. · Zbl 1278.65052
[4] P. Chen, C. K. Cheng, D. Park, and X. Wang, Transient circuit simulation for differential algebraic systems using matrix exponential, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2018, 99.
[5] L. O. Chua and P.-M. Lin, Computer Aided Analysis of Electric Circuits: Algorithms and Computational Techniques, Prentice-Hall, Englewood Cliffs, NJ, 1975. · Zbl 0358.94002
[6] W. Cody, G. Meinardus, and R. Varga, Chebyshev rational approximations to \(e^{-x}\) in \([0, +\infty)\) and applications to heat-conduction problems, J. Approximation Theory, 2 (1969), pp. 50-65, https://doi.org/10.1016/0021-9045(69)90030-6. · Zbl 0187.11602
[7] M. Crouzeix, Numerical range and functional calculus in Hilbert space, J. Funct. Anal., 244 (2007), pp. 668-690, https://doi.org/10.1016/j.jfa.2006.10.013. · Zbl 1116.47004
[8] V. Druskin and L. Knizhnerman, Extended Krylov subspaces: Approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771, https://doi.org/10.1137/S0895479895292400. · Zbl 0912.65022
[9] T. Ericsson, A generalised eigenvalue problem and the Lanczos algorithm, in Large Scale Eigenvalue Problems, North-Holland Math. Stud. 127, J. Cullum and R. A. Willoughby, eds., North-Holland, Amsterdam, 1986, pp. 95-119, https://doi.org/10.1016/S0304-0208(08)72642-2. · Zbl 0605.65026
[10] T. Ericsson and A. Ruhe, The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp., 35 (1980), pp. 1251-1268, https://doi.org/10.2307/2006390. · Zbl 0468.65021
[11] R. W. Freund, Krylov-subspace methods for reduced-order modeling in circuit simulation, J. Comput. Appl. Math., 123 (2000), pp. 395-421. · Zbl 0964.65082
[12] R. A. Friesner, L. S. Tuckerman, B. C. Dornblaser, and T. V. Russo, A method for exponential propagation of large systems of stiff nonlinear differential equations, J. Sci. Comput., 4 (1989), pp. 327-354, https://doi.org/10.1007/BF01060992.
[13] T. Göckler, Rational Krylov Subspace Methods for Phi-Functions in Exponential Integrators, Ph.D. thesis, Karlsruher Institut für Technologie, Karlsruhe, Germany, 2014, https://doi.org/10.5445/IR/1000043647. · Zbl 1416.65192
[14] V. Grimm, Resolvent Krylov subspace approximation to operator functions, BIT, 52 (2012), pp. 639-659, https://doi.org/10.1007/s10543-011-0367-8. · Zbl 1258.65052
[15] V. Grimm and T. Göckler, Automatic smoothness detection of the resolvent Krylov subspace method for the approximation of \(C_0\)-semigroups, SIAM J. Numer. Anal., 55 (2017), pp. 1483-1504, https://doi.org/10.1137/15M104880X. · Zbl 1367.65070
[16] V. Grimm and M. Hochbruck, Rational approximation to trigonometric operators, BIT, 48 (2008), pp. 215-229, https://doi.org/10.1007/s10543-008-0185-9. · Zbl 1148.65075
[17] M. S. Gupta, J. L. Oatley, R. Joseph, G.-Y. Wei, and D. M. Brooks, Understanding voltage variations in chip multiprocessors using a distributed power-delivery network, in Proceedings of IEEE Design, Automation, and Test in Europe Conference & Exhibition, 2007, pp. 1-6.
[18] S. Güttel, Rational Krylov approximation of matrix functions: Numerical methods and optimal pole selection, GAMM-Mitt., 36 (2013), pp. 8-31, https://doi.org/10.1002/gamm.201310002. · Zbl 1292.65043
[19] N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778. · Zbl 1167.15001
[20] M. Hochbruck and C. Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 34 (1997), pp. 1911-1925, https://doi.org/10.1137/S0036142995280572. · Zbl 0888.65032
[21] M. Hochbruck and A. Ostermann, Exponential integrators, Acta Numer., 19 (2010), pp. 209-286, https://doi.org/10.1017/S0962492910000048. · Zbl 1242.65109
[22] M. Hochbruck, A. Ostermann, and J. Schweitzer, Exponential Rosenbrock-type methods, SIAM J. Numer. Anal., 47 (2009), pp. 786-803, https://doi.org/10.1137/080717717. · Zbl 1193.65119
[23] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, UK, 2013, https://doi.org/10.1017/9781139020411. · Zbl 1267.15001
[24] A. Ilchmann and T. Reis, eds., Surveys in Differential-Algebraic Equations II, Springer, Cham, 2015. · Zbl 1305.65006
[25] J. Jimenez, H. de la Cruz, and P. D. Maio, Efficient computation of phi-functions in exponential integrators, J. Comput. Appl. Math., 374 (2020), 112758, https://doi.org/10.1016/j.cam.2020.112758. · Zbl 1503.65015
[26] C. R. Johnson, Numerical determination of the field of values of a general complex matrix, SIAM J. Numer. Anal., 15 (1978), pp. 595-602, https://doi.org/10.1137/0715039. · Zbl 0389.65018
[27] A. B. Kahng, S. Kang, H. Lee, I. L. Markov, and P. Thapar, High-performance gate sizing with a signoff timer, in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2013, pp. 450-457.
[28] D. Kouroussis and F. N. Najm, A static pattern-independent technique for power grid voltage integrity verification, in Proceedings of the IEEE/ACM Design Automation Conference, 2003, pp. 99-104.
[29] P. D. Lax and B. Wendroff, Difference schemes for hyperbolic equations with high order of accuracy, Comm. Pure Appl. Math., 17 (1964), pp. 381-398, https://doi.org/10.1002/cpa.3160170311. · Zbl 0233.65050
[30] Z. Li, R. Balasubramanian, F. Liu, and S. Nassif, 2012 tau power grid simulation contest: Benchmark suite and results, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2012, pp. 643-646.
[31] S. Lin and N. Chang, Challenges in power-ground integrity, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2001, pp. 651-654.
[32] S. Lin, M. Nagata, K. Shimazake, K. Satoh, M. Sumita, H. Tsujikawa, and A. T. Yang, Full-chip vectorless dynamic power integrity analysis and verification against 100uV/100ps-resolution measurement, in Proceedings of the IEEE Custom Integrated Circuits Conference, 2004, pp. 509-512.
[33] J. Lu, P. Chen, C.-C. Chang, L. Sha, D. Huang, C.-C. Teng, and C.-K. Cheng, ePlace: Electrostatics based placement using Nesterov’s method, in Proceedings of the IEEE/ACM Design Automation Conference, 2014, pp. 1-6.
[34] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, and C. K. Cheng, ePlace-MS: Electrostatics based placement for mixed-size circuits, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 34 (2015), pp. 685-698.
[35] J. Lu, H. Zhuang, I. Kang, P. Chen, and C.-K. Cheng, ePlace-3D: Electrostatics based placement for 3D-ICs, in Proceedings of the ACM International Symposium on Physical Design, 2016, pp. 11-18.
[36] K. Meerbergen and A. Spence, Implicitly restarted Arnoldi with purification for the shift-invert transformation, Math. Comp., 66 (1997), pp. 667-689. · Zbl 0864.65020
[37] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, SIAM Rev., 20 (1978), pp. 801-836, https://doi.org/10.1137/1020098. · Zbl 0395.65012
[38] C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45 (2003), pp. 3-49, https://doi.org/10.1137/S00361445024180. · Zbl 1030.65029
[39] I. Moret and P. Novati, RD-rational approximations of the matrix exponential, BIT, 44 (2004), pp. 595-615. · Zbl 1075.65062
[40] L. Nagel, SPICE2: A Computer Program to Simulate Semiconductor Circuits, Ph.D. dissertation, University of California, Berkeley, CA, 1975.
[41] F. N. Najm, Circuit Simulation, Wiley, New York, 2010.
[42] S. R. Nassif, Power grid analysis benchmarks, in Proceedings of the Asia and South Pacific Design Automation Conference, 2008, pp. 376-381.
[43] S. R. Nassif and J. N. Kozhaya, Fast power grid simulation, in Proceedings of the IEEE/ACM Design Automation Conference, 2000, pp. 156-161.
[44] J. Nissen and W. M. Wright, A Krylov subspace algorithm for evaluating the phi function appearing in exponential integrators, ACM Trans. Math. Software, 38 (2012), pp. 1-21.
[45] B. Nour-Omid, B. N. Parlett, T. Ericsson, and P. S. Jensen, How to implement the spectral transformation, Math. Comp., 48 (1987), pp. 663-673. · Zbl 0638.65026
[46] M. Pan, N. Viswanathan, and C. Chu, An efficient and effective detailed placement algorithm, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2005, pp. 48-55.
[47] C. Pearcy, An elementary proof of the power inequality for the numerical radius., Michigan Math. J., 13 (1966), pp. 289-291, https://doi.org/10.1307/mmj/1031732779. · Zbl 0143.16205
[48] J. Rommes and N. Martins, Exploiting structure in large-scale electrical circuit and power system problems, Linear Algebra Appl., 431 (2009), pp. 318-333. · Zbl 1185.93010
[49] A. Ruhe, Rational Krylov sequence methods for eigenvalue computation, Linear Algebra Appl., 58 (1984), pp. 391-405, https://doi.org/10.1016/0024-3795(84)90221-0. · Zbl 0554.65025
[50] Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal., 29 (1992), pp. 209-228, https://doi.org/10.1137/0729014. · Zbl 0749.65030
[51] S. K. Samal, K. Samadi, P. Kamal, Y. Du, and S. K. Lim, Full chip impact study of power delivery network designs in monolithic 3D ICs, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2014, pp. 565-572.
[52] L. M. Silveira, M. Kamon, I. Elfadel, and J. White, A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits, Comput. Methods Appl. Mech. Engrg., 169 (1999), pp. 377-389. · Zbl 0941.78013
[53] B. Simeon, C. Führer, and P. Rentrop, The Drazin inverse in multibody system dynamics, Numer. Math., 64 (1993), pp. 521-539. · Zbl 0797.65054
[54] M. Spijker, Numerical ranges and stability estimates, Appl. Numer. Math., 13 (1993), pp. 241-249, https://doi.org/10.1016/0168-9274(93)90146-I. · Zbl 0789.65060
[55] M. Takamatsu and S. Iwata, Index characterization of differential-algebraic equations in hybrid analysis for circuit simulation, Int. J. Circuit Theory Appl., 38 (2010), pp. 419-440. · Zbl 1191.94167
[56] L. N. Trefethen, Approximation Theory and Approximation Practice, SIAM, Philadelphia, 2012. · Zbl 1437.41001
[57] J. van den Eshof and M. Hochbruck, Preconditioning Lanczos approximations to the matrix exponential, SIAM J. Sci. Comput., 27 (2006), pp. 1438-1457, https://doi.org/10.1137/040605461. · Zbl 1105.65051
[58] K. Wang, B. H. Meyer, R. Zhang, K. Skadron, and M. R. Stan, Walking pads: Fast power-supply pad-placement optimization, in Proceedings of the IEEE/ACM Asia and South Pacific Design Automation Conference, 2014, pp. 537-543.
[59] X. Wang, P. Chen, and C. K. Cheng, Stability and convergency exploration of matrix exponential integration on power delivery network transient simulation, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 39 (2020), pp. 2735-2748, https://doi.org/10.1109/TCAD.2019.2954473.
[60] G. Wanner, Dahlquist’s classical papers on stability theory, BIT, 46 (2006), pp. 671-683. · Zbl 1112.65074
[61] S.-H. Weng, Q. Chen, and C. K. Cheng, Time-domain analysis of large-scale circuits by matrix exponential method with adaptive control, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 31 (2012), pp. 1180-1193.
[62] R. Winkler, Stochastic differential algebraic equations of index 1 and applications in circuit simulation, J. Comput. Appl. Math., 157 (2003), pp. 477-505. · Zbl 1043.65010
[63] L. Xiao, Z. Xiao, Z. Qian, Y. Jiang, T. Huang, H. Tian, and E. F. Y. Young, Local clock skew minimization using blockage-aware mixed tree-mesh clock network, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2010, pp. 458-462.
[64] W. Yu, H. Zhuang, C. Zhang, G. Hu, and Z. Liu, RWCap: A floating random walk solver for 3-D capacitance extraction of very-large-scale integration interconnects, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 32 (2013), pp. 353-366.
[65] Z. Zeng, X. Ye, Z. Feng, and P. Li, Tradeoff analysis and optimization of power delivery networks with on-chip voltage regulation, in Proceedings of the IEEE/ACM Design Automation Conference, 2010, pp. 831-836.
[66] C. Zhang and W. Yu, Efficient space management techniques for large-scale interconnect capacitance extraction with floating random walks, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 32 (2013), pp. 1633-1637.
[67] R. Zhang, B. H. Meyer, W. Huang, K. Skadron, and M. R. Stan, Some limits of power delivery in the multicore era, in Proceedings of the 4th Workshop on Energy-Efficient Design, 2012.
[68] R. Zhang, K. Wang, B. H. Meyer, M. R. Stan, and K. Skadron, Architecture implications of pads as a scarce resource, in Proceedings of the International Symposium on Computer Architecture, 2014, pp. 373-384.
[69] Y. Zhang and C. Chu, GDRouter: Interleaved global routing and detailed routing for ultimate routability, in Proceedings of the IEEE/ACM Design Automation Conference, 2012, pp. 597-602.
[70] H. Zhuang, J. Lu, K. Samadi, Y. Du, and C. K. Cheng, Performance-driven placement for design of rotation and right arithmetic shifters in monolithic \(3\) D ICs, in Proceedings of the IEEE International Conference on Communications, Circuits and Systems, Vol. 2, 2013, pp. 509-513.
[71] H. Zhuang, W. Yu, G. Hu, Z. Liu, and Z. Ye, Fast floating random walk algorithm for multi-dielectric capacitance extraction with numerical characterization of Green’s functions, in Proceedings of the IEEE/ACM Asia and South Pacific Design Automation Conference, 2012, pp. 377-382.
[72] H. Zhuang, W. Yu, S.-H. Weng, I. Kang, J.-H. Lin, X. Zhang, R. Coutts, J. Lu, and C. K. Cheng, Simulation algorithms with exponential integration for time-domain analysis of large-scale power delivery networks, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 35 (2016), pp. 1681-1694.
[73] C. Zhuo, H. Gan, and W.-K. Shih, Early-stage power grid design: Extraction, modeling and optimization, in Proceedings of the IEEE/ACM Design Automation Conference, 2014, pp. 1-6.
[74] C. Zhuo, G. Wilke, R. Chakraborty, A. Aydiner, S. Chakravarty, and W.-K. Shih, A silicon-validated methodology for power delivery modeling and simulation, in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2012, pp. 255-262.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.