Abstract
A non-splitting method for tridiagonalizing complex symmetric (non-Hermitian) matrices is developed and analyzed. The main objective is to exploit the purely structural symmetry in terms of runtime performance. Based on the analytical derivation of the method, Fortran implementations of a blocked variant are developed and extensively evaluated experimentally. In particular, it is illustrated that a straightforward implementation based on the analytical derivation exhibits deficiencies in terms of numerical properties. Nevertheless, it is also shown that the blocked non-splitting method shows very promising results in terms of runtime performance. On average, a speed-up of more than three is achieved over competing methods. Although more work is needed to improve the numerical properties of the non-splitting tridiagonalization method, the runtime performance achieved with this non-unitary tridiagonalization process is very encouraging and indicates important research directions for this class of eigenproblems.
Chapter PDF
Similar content being viewed by others
References
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)
Gansterer, W.N., Schabauer, H., Pacher, C., Finger, N.: Tridiagonalizing complex symmetric matrices in waveguide simulations. In: Bubak, M., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2008, Part I. LNCS, vol. 5101, pp. 945–954. Springer, Heidelberg (2008)
Freund, R.W., Nachtigal, N.M.: QMRPACK: a package of QMR algorithms. ACM Trans. Math. Softw. 22(1), 46–77 (1996)
Dongarra, J.J., Du Croz, J., Duff, I.S., Hammarling, S.: A set of level 3 basic linear algebra subprograms. ACM Trans. Math. 16, 1–17, 18–28 (1990)
Anderson, E., Bai, Z., Bischof, C.H., Blackford, S., Demmel, J.W., Dongarra, J.J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.C.: Lapack Users Guide, 3rd edn. SIAM Press, Philadelphia (1999)
Blackford, L.S., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J.W., Dhillon, I., Dongarra, J.J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLapack Users’ Guide. SIAM Press, Philadelphia (1997)
van de Geijn, R.: Using PLapack: Parallel Linear Algebra Package. The MIT Press, Cambridge (1997)
Freund, R.W., Gutknecht, M.H., Nachtigal, N.M.: An implementation of the look-ahead Lanczos algorithm for non-hermitian matrices. SIAM J. Sci. Comput. 14(1), 137–158 (1993)
Cullum, J.K., Willoughby, R.A.: A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices. In: Cullum, J.K., Willoughby, R.A. (eds.) Proceedings of the IBM Europe Institute Workshop on Large Scale Eigenvalue Problems, pp. 193–223. North-Holland, Amsterdam (1986)
Leung, A.Y.T.: Subspace iteration for complex symmetric eigenproblems. J. Sound Vibration 184(4), 627–637 (1995)
Arbenz, P., Hochstenbach, M.E.: A Jacobi–Davidson method for solving complex symmetric eigenvalue problems. SIAM J. Sci. Comput. 25(5), 1655–1673 (2004)
Bai, Z., Demmel, J., Dongarra, J.J., Ruhe, A., van der Vorst, H. (eds.): Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM Press, Philadelphia (2000)
Ohnami, K., Mikami, Y.: Resonance scattering in a two-dimensional non-integrable system. J. Phys. A 25, 4903–4912 (1992)
Bar-On, I., Ryaboy, V.: Fast diagonalization of large and dense complex symmetric matrices, with applications to quantum reaction dynamics. SIAM J. Sci. Comput. 18, 1412–1435 (1997)
Cullum, J.K., Willoughby, R.A.: A QL procedure for computing the eigenvalues of complex symmetric tridiagonal matrices. SIAM J. Matrix Anal. Appl. 17, 83–109 (1996)
Luk, F., Qiao, S.: Using complex-orthogonal transformations to diagonalize a complex symmetric matrix. In: Luk, F.T. (ed.) Advanced Signal Processing: Algorithms, Architectures, and Implementations VII, Proc. SPIE, vol. (3162), pp. 418–425 (1997)
Cullum, J.K., Willoughby, R.A.: Lanczos Algorithms for Large Symmetric Eigenvalue Computations, vol. 1: Theory, vol. 2: Programs. Birkhäuser, Boston (1985)
La Budde, C.D.: The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations. Math. Comp. 17, 433–437 (1963)
Wang, H.H., Gregory, R.T.: On the reduction of an arbitrary real square matrix to tridiagonal form. Math. Comp. 18, 501–505 (1964)
Parlett, B.N.: A note on La Budde’s algorithm. Math. Comp. 18, 505–506 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gansterer, W.N., Gruber, A.R., Pacher, C. (2009). Non-splitting Tridiagonalization of Complex Symmetric Matrices. In: Allen, G., Nabrzyski, J., Seidel, E., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds) Computational Science – ICCS 2009. Lecture Notes in Computer Science, vol 5544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01970-8_47
Download citation
DOI: https://doi.org/10.1007/978-3-642-01970-8_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01969-2
Online ISBN: 978-3-642-01970-8
eBook Packages: Computer ScienceComputer Science (R0)