×

An alternating maximization method for approximating the hump of the matrix exponential. (English) Zbl 1378.65097

If \(A\in\mathbb{C}^{n\times n}\) is stable (eigenvalues in the left-half plane), then the curve \(\Gamma(t)=\|e^{tA}\|_2\), \(t\geq0\) has humps where local maxima \(\Gamma_h=\Gamma(t_h)\) are attained. Define \(\gamma(t,v)=\|e^{tA}v\|_2\), with \(t\geq0\) and \(v\in\mathbb{C}^n\), \(\|v\|_2=1\), then \(\max_{\|v\|_2=1}\gamma(t_h,v)=\gamma(t_h,v_h)=\Gamma_h=\max_{t\in I}\gamma(t,v_h)\) where \(I\) is an interval containing \(t_h\). Note that \(v_h\) is a right singular vector of \(e^{t_hA}\) with singular value \(\Gamma_h\). This is used to compute a (local) hump iteratively by alternatingly computing the maximum of \(\gamma(t,v)\) over \(v\) for \(t\) fixed, and use the result to fix \(v\) and compute a maximum over \(t\). A convergence analysis is given and it is proved that the method converges to the local maximum or alternates between accumulation points where \(\gamma(t,v)\) is not maximal. Implementation aspects (e.g. finding a starting vector for \(v\) and a stopping criterion) are discussed and the method is extensively tested numerically.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
65K10 Numerical optimization and variational techniques
49J05 Existence theories for free problems in one independent variable
15A18 Eigenvalues, singular values, and eigenvectors

Software:

Expokit; Eigtool
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boiko, A., Nechepurenko, Y., Sadkane, M.: Fast computation of optimal disturbances for duct flows with a given accuracy. Comput. Math. Math. Phys. 50, 1914-1924 (2010) · Zbl 1224.76045 · doi:10.1134/S096554251011014X
[2] Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[3] Ciarlet, P.G.: Introduction to Numerical Linear Algebra and Optimisation. Cambridge University Press, New York (1989)
[4] Douglas, J., Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. Am. Math. Soc. 82, 421-439 (1956) · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4
[5] Forsythe, G.E., Malcolm, M.A., Moler, M.A.: Computer Methods for Mathematical Computations. Prentice Hall, New York (1976) · Zbl 0361.65002
[6] Godunov, S.K.: Ordinary differential equations with constant coefficient. Translations of Mathematical Monographs, vol. 169. American Mathematical Society, Providence, RI (1997) · Zbl 0884.34001
[7] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[8] Kato, T.: Perturbation Theory for Linear Operators. Springer, New York (1966) · Zbl 0148.12601 · doi:10.1007/978-3-662-12678-3
[9] Li, Y., Osher, S.: Coordinate descent optimization for 1 minimization with application to compressed sensing; a greedy algorithm. Inverse Probl. Imaging 3, 487-503 (2009) · Zbl 1188.90196 · doi:10.3934/ipi.2009.3.487
[10] Mao, X., Sherwin, S.J.: Transient growth associated with continuous spectra of the Batchelor vortex. J. Fluid Mech. 697, 35-59 (2012) · Zbl 1250.76057 · doi:10.1017/jfm.2012.33
[11] Moler, C., van Loan, C.: Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Rev. 45, 3-49 (2003) · Zbl 1030.65029 · doi:10.1137/S00361445024180
[12] Monokrousos, A., Åkervik, E., Brandt, L., Henningson, S.: Global three-dimensional optimal disturbances in the Blasius boundary-layer flow using time-steppers. J. Fluid Mech. 650, 181-214 (2010) · Zbl 1189.76192 · doi:10.1017/S0022112009993703
[13] Nechepurenko, YuN, Sadkane, M.: A low-rank approximation for computing the matrix exponential norm. SIAM J. Matrix Anal. Appl. 32, 349-363 (2011) · Zbl 1298.65085 · doi:10.1137/100789774
[14] Nechepurenko, Yu.M., Sadkane, M.: Computing humps of the matrix exponential. J. Comput. Appl. Math. (2017). doi:10.1016/j.cam.2016.12.031 · Zbl 1360.65136
[15] Ostrowski, A.M.: Solution of Equations and Systems of Equations, 2nd edn. Academic Press, New York (1966) · Zbl 0222.65070
[16] Peaceman, D.H., Rachford, H.H.: The numerical solution of parabolic elliptic differential equations. SIAM J. Appl. Math. 3, 28-41 (1955) · Zbl 0067.35801 · doi:10.1137/0103003
[17] Schmid, P., Henningson, D.S.: Stability and Transition in Shear Flows. Springer, Berlin (2000) · Zbl 0966.76003
[18] Sidje, R.B.: EXPOKIT: A software package for computing matrix exponentials. ACM Trans. Math. Softw. 24(1), 130-156 (1998) · Zbl 0917.65063 · doi:10.1145/285861.285868
[19] Stewart, G.W., Sun, Ji-guang: Matrix Perturbation Theory. Academic Press, London (1990) · Zbl 0706.65013
[20] Trefethen, L.N., Embree, M.: Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, Princeton (2005) · Zbl 1085.15009
[21] Tseng, P., Yun, S.: A block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl. 140, 513-535 (2009) · Zbl 1190.90279 · doi:10.1007/s10957-008-9458-3
[22] van Dorsselaer, J.L.M., Kraaijevanger, J.F.B.M., Spijker, M.N.: Linear stability analysis in the numerical solution of initial value problems. Acta Numer. 2, 199-237 (1993) · Zbl 0796.65091 · doi:10.1017/S0962492900002361
[23] Van Loan, C.F.: The sensitivity of the matrix exponential. SIAM J. Numer. Anal. 14(6), 971-981 (1977) · Zbl 0368.65006 · doi:10.1137/0714065
[24] Yecko, P., Zaleski, S.: Transient growth in two-phase mixing layers. J. Fluid Mech. 528, 43-52 (2005) · Zbl 1163.76424 · doi:10.1017/S0022112005003307
[25] Wachspress, E.L.: Extended application of alternating direction implicit iteration model problem theory. J. SIAM 11, 994-1016 (1963) · Zbl 0244.65045
[26] Wachspress, E.L.: Iterative solution of the Lyapunov matrix equations. Appl. Math. Lett. 107, 87-90 (1988) · Zbl 0631.65037 · doi:10.1016/0893-9659(88)90183-8
[27] Zsolt, U., Lasdon, L., Plummer, J.C., Glover, F., Kelly, J., Mart, R.: Scatter search and local NLP solvers: a multistart framework for global optimization. INFORMS J. Comput. 19, 328-340 (2007) · Zbl 1241.90093 · doi:10.1287/ijoc.1060.0175
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.