# zbMATH — the first resource for mathematics

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
Eigtool; Expokit
Full Text:
##### References:
  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  Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont (1999) · Zbl 1015.90077  Ciarlet, P.G.: Introduction to Numerical Linear Algebra and Optimisation. Cambridge University Press, New York (1989)  Douglas, J; Rachford, HH, 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  Forsythe, G.E., Malcolm, M.A., Moler, M.A.: Computer Methods for Mathematical Computations. Prentice Hall, New York (1976) · Zbl 0361.65002  Godunov, S.K.: Ordinary differential equations with constant coefficient. Translations of Mathematical Monographs, vol. 169. American Mathematical Society, Providence, RI (1997) · Zbl 0884.34001  Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009  Kato, T.: Perturbation Theory for Linear Operators. Springer, New York (1966) · Zbl 0148.12601  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  Mao, X; Sherwin, SJ, Transient growth associated with continuous spectra of the batchelor vortex, J. Fluid Mech., 697, 35-59, (2012) · Zbl 1250.76057  Moler, C; 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  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  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  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  Ostrowski, A.M.: Solution of Equations and Systems of Equations, 2nd edn. Academic Press, New York (1966) · Zbl 0222.65070  Peaceman, DH; Rachford, HH, The numerical solution of parabolic elliptic differential equations, SIAM J. Appl. Math., 3, 28-41, (1955) · Zbl 0067.35801  Schmid, P., Henningson, D.S.: Stability and Transition in Shear Flows. Springer, Berlin (2000) · Zbl 0966.76003  Sidje, RB, EXPOKIT: A software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 130-156, (1998) · Zbl 0917.65063  Stewart, G.W., Sun, Ji-guang: Matrix Perturbation Theory. Academic Press, London (1990) · Zbl 0706.65013  Trefethen, L.N., Embree, M.: Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, Princeton (2005) · Zbl 1085.15009  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  Dorsselaer, JLM; Kraaijevanger, JFBM; Spijker, MN, Linear stability analysis in the numerical solution of initial value problems, Acta Numer., 2, 199-237, (1993) · Zbl 0796.65091  Loan, CF, The sensitivity of the matrix exponential, SIAM J. Numer. Anal., 14, 971-981, (1977) · Zbl 0368.65006  Yecko, P; Zaleski, S, Transient growth in two-phase mixing layers, J. Fluid Mech., 528, 43-52, (2005) · Zbl 1163.76424  Wachspress, EL, Extended application of alternating direction implicit iteration model problem theory, J. SIAM, 11, 994-1016, (1963) · Zbl 0244.65045  Wachspress, EL, Iterative solution of the Lyapunov matrix equations, Appl. Math. Lett., 107, 87-90, (1988) · Zbl 0631.65037  Zsolt, U; Lasdon, L; Plummer, JC; 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.