Efficient algorithm for simultaneous reduction to the \(m\) -Hessenberg-triang

详细信息    查看全文

• 作者：Nela Bosner
• 关键词：$$m$$ m ; Hessenberg ; triangular ; triangular form ; Orthogonal transformations ; Level 3 BLAS ; Blocked algorithm ; Solving shifted system ; Transfer function evaluation ; Staircase form ; 15A21 ; 15A06 ; 65F05 ; 65Y20 ; 93B05 ; 93B10 ; 93B17 ; 93B40
• 刊名：BIT Numerical Mathematics
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：55
• 期：3
• 页码：677-703
• 全文大小：3,177 KB
• 参考文献：1.Ahuja, K., De Sturler, E., Gugercin, S., Chang, E.R.: Recycling BiCG with an application to model reduction. SIAM J. Sci. Comput. 34, A1925–A1949 (2012)
  2.Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J.J., Du Croz, J., Greenbaum, A., Hammarling, S.J., McKenney, A., Sorensen, D.C.: LAPACK Users-Guide, 3rd edn. SIAM, Philadelphia (1999)CrossRef
  3.Beattie, C.A., Drma?, Z., Gugercin, S.: A note on shifted Hessenberg systems and frequency response computation. ACM Trans. Math. Softw. 38, 12:1-2:16 (2011)
  4.Bosner, N., Bujanovi?, Z., Drma?, Z.: Efficient generalized Hessenberg form and applications. ACM Trans. Math. Softw. 39, 19:1-9:19 (2013)
  5.Chu, K.-W.E.: A controllability condensed form and a state feedback pole assignment algorithm for descriptor systems. IEEE Trans. Autom. Control 33, 366-70 (1988)MATH CrossRef
  6.Dackland, K., K?gstr?m, B.: Blocked algorithms and software for reduction of a regular matrix pair to generalized Schur form. ACM Trans. Math. Softw. 25, 425-54 (1999)MATH CrossRef
  7.Dongarra, J.J., Du Croz, J., Duff, I., Hammarling, S.: A set of Level 3 basic linear algebra subprograms. ACM Trans. Math. Soft. 16, 1-7 (1990)
  8.Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. M. D. Johns Hopkins University Press, Baltimore (1996)MATH
  9.Gugercin, S., Antoulas, A.C., Beattie, C.A.: H2 model reduction for large-scale linear dynamical systems. SIAM J. Matrix Anal. Appl. 30, 609-38 (2008)MATH MathSciNet CrossRef
  10.Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002)MATH CrossRef
  11.K?gstr?m, B., Kressner, D., Quintana-Ortí, E.S., Quintana-Ortí, G.: Blocked algorithms for the reduction to Hessenberg-triangular form revisited. BIT 48, 563-84 (2008)MATH MathSciNet CrossRef
  12.Karlsson, L., K?gstr?m, B.: Parallel two-stage reduction to Hessenberg form using dynamic scheduling on shared-memory architectures. Parallel Comput. 37, 771-82 (2011)MATH CrossRef
  13.Lang, B.: Using level 3 BLAS in rotation-based algorithms. SIAM J. Sci. Comput. 19, 626-34 (1998)MATH MathSciNet CrossRef
  14.Laub, A.J., Linnemann, A.: Hessenberg and Hessenberg/triangular forms in linear system theory. Int. J. Control 44, 1523-547 (1986)MATH MathSciNet CrossRef
  15.Miminis, G.S.: Deflation in eigenvalue assignment of descriptor systems using state feedback. IEEE Trans. Autom. Control 38, 1322-336 (1993)MATH MathSciNet CrossRef
  16.Miminis, G.S., Paige, C.C.: An algorithm for pole assignment of time invariant linear systems. Int. J. Control 35, 341-54 (1982)MATH MathSciNet CrossRef
  17.Miminis, G.S., Paige, C.C.: An algorithm for pole assignment of time invariant multi-input linear systems. In: Proceedings 21st IEEE Conference on Decision and Control, pp. 62-7 (1982)
  18.Paige, C.C.: Properties of numerical algorithms related to computing controllability. IEEE Trans. Autom. Control 26, 130-38 (1981)MATH MathSciNet CrossRef
  19.Parallelism in the Intel\(\textregistered {}\) Math Kernel Library. http://?software.?intel.?com/?en-us/?articles/?parallelism-in-the-intel-math-kernel-library
  20.Simoncini, V.: Restarted full orthogonalization method for shifted linear systems. BIT 43, 459-66 (2003)MATH MathSciNet CrossRef
  21.Simoncini, V., Perotti, F.: On the numerical solution of \((\lambda ^{2}A+\lambda B+C)x=b\) and application to structural dynamics. SIAM J. Sci. Comput. 23, 1875-897 (2002)
  22.SLICOT. http://?www.?slicot.?org
  23.van Dooren, P.M., Verhaegen, M.: On the use of unitary state-space transformations, Linear algebra and its role in systems theory, Proc. AMS-IMS-SIAM Conf., Brunswick/Maine 1984. Contemp. Math. 47, 447-63 (1985)CrossRef
  24.van Gijzen, M.B., Erlangga, Y.A., Vuik, C.: Spectral analysis of the discrete Helmholtz operator preconditioned with a shifted Laplacian. SIAM J. Sci. Comput. 29, 1942-958 (2007)
  25.Van Zee, F.G., van de Geijn, R.A., Quintana-Orti, G.: Restructuring the tridiagonal and bidiagonal QR algorithms for performance. ACM Trans. Math. Softw. 40, 18:1-8:34 (2014)
  26.Varga, A.: Numerical algorithms and software tools for analysis and modelling of descriptor systems. Prepr. of 2nd IFAC Workshop on System Structure and Control, Prague, pp. 392-95 (1992)
  27.Varga, A.: Computation of irreducible generalized state-space realizations. Kybernetika 26, 89-06 (1990)MATH MathSciNet
  28.Varga, A., Van Dooren, P.M.: Task I.A—basic software tools for standard and generalized state-space systems and transfer matrix factorizations, SLICOT Working Note 17 (1999)
  
• 作者单位：Nela Bosner (1)
  
  1. Department of Mathematics, University of Zagreb, Zagreb, Croatia
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  Numeric Computing
  Mathematics
  
• 出版者：Springer Netherlands
• ISSN：1572-9125

文摘

This paper proposes an efficient algorithm for simultaneous reduction of three matrices by using orthogonal transformations, where \(A\) is reduced to \(m\)-Hessenberg form, and \(B\) and \(E\) to triangular form. The algorithm is a blocked version of the algorithm described by Miminis and Paige (Int J Control 35:341-54, 1982). The \(m\)-Hessenberg-triangular–triangular form of matrices \(A\), \(B\) and \(E\) is specially suitable for solving multiple shifted systems \((\sigma E-A)X=B\). Such shifted systems naturally occur in control theory when evaluating the transfer function of a descriptor system, or in interpolatory model reduction methods. They also arise as a result of discretizing the time-harmonic wave equation in heterogeneous media, or originate from structural dynamics engineering problems. The proposed blocked algorithm for the \(m\)-Hessenberg-triangular-triangular reduction is based on aggregated Givens rotations, and is a generalization of the blocked algorithm for the Hessenberg-triangular reduction proposed by K?gstr?m et al. (BIT 48:563-84, 2008). Numerical tests confirm that the blocked algorithm is much faster than its non-blocked version based on regular Givens rotations only. As an illustration of its efficiency, two applications of the \(m\)-Hessenberg-triangular-triangular reduction from control theory are described: evaluation of the transfer function of a descriptor system at many complex values, and computation of the staircase form used to identify the controllable part of the system. Keywords \(m\)-Hessenberg-triangular-triangular form Orthogonal transformations Level 3 BLAS Blocked algorithm Solving shifted system Transfer function evaluation Staircase form