×

Generalized rational Krylov decompositions with an application to rational approximation. (English) Zbl 1319.65028

Summary: Generalized rational Krylov decompositions are matrix relations which, under certain conditions, are associated with rational Krylov spaces. We study the algebraic properties of such decompositions and present an implicit Q theorem for rational Krylov spaces. Transformations on rational Krylov decompositions allow for changing the poles of a rational Krylov space without recomputation, and two algorithms are presented for this task. Using such transformations we develop a rational Krylov method for rational least squares fitting. Numerical experiments indicate that the proposed method converges fast and robustly. A MATLAB toolbox with implementations of the presented algorithms and experiments is provided.

MSC:

65F18 Numerical solutions to inverse eigenvalue problems
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65D10 Numerical smoothing, curve fitting

Software:

RKToolbox; Matlab; NLEIGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Beckermann and L. Reichel, {\it Error estimates and evaluation of matrix functions via the Faber transform}, SIAM J. Numer. Anal., 47 (2009), pp. 3849-3883. · Zbl 1204.65041
[2] M. Berljafa and S. Güttel, {\it A Rational Krylov Toolbox for MATLAB}, MIMS EPrint 2014.56, Manchester Institute for Mathematical Sciences, The University of Manchester, Manchester, UK, 2014. Available for download at http://guettel.com/rktoolbox/.
[3] M. Berljafa and S. Güttel, {\it The RKFIT Algorithm for Nonlinear Rational Approximation}, MIMS EPrint 2015.38, Manchester Institute for Mathematical Sciences, The University of Manchester, Manchester, UK, 2015. · Zbl 1373.65037
[4] R.-U. Börner, O. G. Ernst, and S. Güttel, {\it Three-dimensional Transient Electromagnetic Modeling Using Rational Krylov Methods}, MIMS EPrint 2014.36, Manchester Institute for Mathematical Sciences, The University of Manchester, Manchester, UK, 2014; Geophys. J. Int., to appear.
[5] Z. Bujanović and Z. Drmač, {\it A new framework for implicit restarting of the Krylov-Schur algorithm}, Numer. Linear Algebra Appl., 22 (2015), pp. 220-232. · Zbl 1363.65059
[6] A. Bultheel, P. Gonzalez-Vera, E. Hendriksen, and O. Njastad, {\it Orthogonal Rational Functions}, Cambridge University Press, Cambridge, UK, 1999. · Zbl 0923.42017
[7] A. Bultheel, M. Van Barel, and P. Van Gucht, {\it Orthogonal basis functions in discrete least-squares rational approximation}, J. Comput. Appl. Math., 164/165 (2004), pp. 175-194. · Zbl 1046.93010
[8] G. De Samblanx and A. Bultheel, {\it Using implicitly filtered RKS for generalised eigenvalue problems}, J. Comput. Appl. Math., 107 (1999), pp. 195-218. · Zbl 0944.65038
[9] G. De Samblanx, K. Meerbergen, and A. Bultheel, {\it The implicit application of a rational filter in the RKS method}, BIT, 37 (1997), pp. 925-947. · Zbl 0890.65035
[10] K. Deckers and A. Bultheel, {\it Rational Krylov Sequences and Orthogonal Rational Runctions}, Tech. report TW499, Department of Computer Science, KU Leuven, Leuven, Belgium, 2007.
[11] D. Deschrijver, B. Haegeman, and T. Dhaene, {\it Orthonormal vector fitting: A robust macromodeling tool for rational approximation of frequency domain responses}, IEEE Trans. Advanced Packaging, 30 (2007), pp. 216-225.
[12] Z. Drmač, S. Gugercin, and C. Beattie, {\it Quadrature-based vector fitting for discretized \(\mathcal{H}_2\) approximation}, SIAM J. Sci. Comput., 37 (2015), pp. A625-A652. · Zbl 1320.93029
[13] V. Druskin and L. Knizhnerman, {\it Extended Krylov subspaces: Approximation of the matrix square root and related functions}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771. · Zbl 0912.65022
[14] V. Druskin, L. Knizhnerman, and M. Zaslavsky, {\it Solution of large scale evolutionary problems using rational Krylov subspaces with optimized shifts}, SIAM J. Sci. Comput., 31 (2009), pp. 3760-3780. · Zbl 1204.65042
[15] J. van den Eshof and M. Hochbruck, {\it Preconditioning Lanczos approximations to the matrix exponential}, SIAM J. Sci. Comput., 27 (2006), pp. 1438-1457. · Zbl 1105.65051
[16] D. Fasino, {\it Rational Krylov matrices and QR steps on Hermitian diagonal-plus-semiseparable matrices}, Numer. Linear Algebra Appl., 12 (2005), pp. 743-754. · Zbl 1164.15339
[17] K. Gallivan, E. Grimme, and P. Van Dooren, {\it A rational Lanczos algorithm for model reduction}, Numer. Algorithms, 12 (1996), pp. 33-63. · Zbl 0870.65053
[18] T. Göckler and V. Grimm, {\it Uniform approximation of \(φ\)-functions in exponential integrators by a rational Krylov subspace method with simple poles}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1467-1489. · Zbl 1416.65192
[19] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[20] P. Gonnet, S. Güttel, and L. N. Trefethen, {\it Robust Padé approximation via SVD}, SIAM Rev., 55 (2013), pp. 101-117. · Zbl 1266.41009
[21] P. Gonnet, R. Pachón, and L. N. Trefethen, {\it Robust rational interpolation and least-squares}, Electron. Trans. Numer. Anal., 38 (2011), pp. 146-167. · Zbl 1293.65017
[22] S. Gugercin, A. Antoulas, and C. Beattie, {\it A rational Krylov iteration for optimal H2 model reduction}, in Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, 2006, pp. 1665-1667.
[23] B. Gustavsen, {\it Improving the pole relocating properties of vector fitting}, IEEE Trans. Power Del., 21 (2006), pp. 1587-1592.
[24] B. Gustavsen, {\it Comments on “A comparative study of vector fitting and orthonormal vector fitting techniques for EMC applications,”} in Proceedings of the 18th International Zurich Symposium on Electromagnetic Compatibility, Zurich, Switzerland, 2007, pp. 131-134.
[25] B. Gustavsen and A. Semlyen, {\it Rational approximation of frequency domain responses by vector fitting}, IEEE Trans. Power Del., 14 (1999), pp. 1052-1061.
[26] S. Güttel, {\it Rational Krylov Methods for Operator Functions}, Ph.D. thesis, Institut für Numerische Mathematik und Optimierung der Technischen Universität Bergakademie Freiberg, Freiberg, Germany, 2010. Available online at http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-27645.
[27] S. Güttel, {\it Rational Krylov approximation of matrix functions: Numerical methods and optimal pole selection}, GAMM-Mitt., 36 (2013), pp. 8-31. · Zbl 1292.65043
[28] S. Güttel, R. V. Beeumen, K. Meerbergen, and W. Michiels, {\it NLEIGS: A class of fully rational Krylov methods for nonlinear eigenvalue problems}, SIAM J. Sci. Comput., 36 (2014), pp. A2842-A2864. · Zbl 1321.47128
[29] C. Jagels and L. Reichel, {\it Recursion relations for the extended Krylov subspace method}, Linear Algebra Appl., 434 (2011), pp. 1716-1732. · Zbl 1211.65039
[30] E. Jarlebring and H. Voss, {\it Rational Krylov for nonlinear eigenproblems, an iterative projection method}, Appl. Math., 50 (2005), pp. 543-554. · Zbl 1099.65037
[31] B. K\aagström and P. Poromaa, {\it Computing eigenspaces with specified eigenvalues of a regular matrix pair (A, B) and condition estimation: Theory, algorithms and software}, Numer. Algorithms, 12 (1996), pp. 369-407. · Zbl 0859.65036
[32] D. Kressner, {\it Block algorithms for reordering standard and generalized Schur forms}, ACM Trans. Math. Software, 32 (2006), pp. 521-532. · Zbl 1230.65048
[33] T. Mach, M. Pranić, and R. Vandebril, {\it Computing approximate (block) rational Krylov subspaces without explicit inversion with extensions to symmetric matrices}, Electron. Trans. Numer. Anal., 43 (2014), pp. 100-124. · Zbl 1302.65078
[34] K. Meerbergen, {\it Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem}, Numer. Linear Algebra Appl., 8 (2001), pp. 33-52. · Zbl 1051.65040
[35] I. Moret and P. Novati, {\it RD-rational approximations of the matrix exponential}, BIT, 44 (2004), pp. 595-615. · Zbl 1075.65062
[36] M. S. Pranić and L. Reichel, {\it Rational Gauss quadrature}, SIAM J. Numer. Anal., 52 (2014), pp. 832-851. · Zbl 1296.65046
[37] A. Ruhe, {\it Rational Krylov sequence methods for eigenvalue computation}, Linear Algebra Appl., 58 (1984), pp. 391-405. · Zbl 0554.65025
[38] A. Ruhe, {\it The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: Complex shifts for real matrices}, BIT, 34 (1994), pp. 165-176. · Zbl 0810.65032
[39] A. Ruhe, {\it Rational Krylov algorithms for nonsymmetric eigenvalue problems. II. Matrix pairs}, Linear Algebra Appl., 198 (1994), pp. 283-295. · Zbl 0810.65031
[40] A. Ruhe, {\it Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils}, SIAM J. Sci. Comput., 19 (1998), pp. 1535-1551. · Zbl 0914.65036
[41] A. Ruhe, {\it The rational Krylov algorithm for nonlinear matrix eigenvalue problems}, J. Math. Sci. (N.Y.), 114 (2003), pp. 1854-1856. · Zbl 1029.65035
[42] A. Ruhe and D. Skoogh, {\it Rational Krylov algorithms for eigenvalue computation and model reduction}, in Applied Parallel Computing Large Scale Scientific and Industrial Problems, B. K\ragström, J. Dongarra, E. Elmroth, and J. Waśniewski, eds., Lecture Notes in Comput. Sci. 1541, Springer, Berlin, Heidelberg, 1998, pp. 491-502.
[43] G. W. Stewart, {\it A Krylov-Schur algorithm for large eigenproblems}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 601-614. · Zbl 1003.65045
[44] G. W. Stewart, {\it Matrix Algorithms. Volume II: Eigensystems}, SIAM, Philadelphia, 2001. · Zbl 0984.65031
[45] G. W. Stewart, {\it Addendum to “A Krylov-Schur algorithm for large eigenproblems,”} SIAM J. Matrix Anal. Appl., 24 (2002), pp. 599-601. · Zbl 1003.65045
[46] M. Van Barel, D. Fasino, L. Gemignani, and N. Mastronardi, {\it Orthogonal rational functions and structured matrices}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 810-829. · Zbl 1071.42015
[47] R. Van Beeumen, K. Meerbergen, and W. Michiels, {\it A rational Krylov method based on Hermite interpolation for nonlinear eigenvalue problems}, SIAM J. Sci. Comput., 35 (2013), pp. A327-A350. · Zbl 1284.47041
[48] R. Vandebril and D. S. Watkins, {\it A generalization of the multishift QR algorithm}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 759-779. · Zbl 1261.65039
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.