Abstract
In this paper, we parallelize a new algorithm for solving non-symmetric Toeplitz linear systems. This algorithm embeds the Toeplitz matrix in a larger structured matrix, then transforms it into an embedded Cauchy-like matrix by means of trigonometric modifications. Finally, the algorithm applies a modified QR transformation to triangularize the augmented matrix. The algorithm combines e.ciency and stability. It has been implemented using standard tools and libraries, thereby producing a portable code. An extensive experimental analysis has been performed on a cluster of personal computers. Experimental results show that we can obtain efficiencies that are similar to other fast parallel algorithms, while obtaining more accurate results with only one iterative refinement step in the solution.
Supported by Spanish projects CICYT TIC 2000-1683-C03-03 2003-08238-C02-02.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Freund, R.W.: A look-ahead Schur-type algorithm for solving general Toeplitz systems. Zeitschrift für Angewandte Mathe. und Mechanik 74, T538–T541 (1994)
Chandrasekaran, S., Sayed, A.H.: A fast stable solver for nonsymmetric Toeplitz and quasi-Toeplitz systems of linear equations. SIAM Journal on Matrix Analysis and Applications 19(1), 107–139 (1998)
Kung, S.Y., Hu, Y.H.: A highly concurrent algorithm and pipelined architecture for solving Toeplitz systems. IEEE Trans. Acoustics, Speech and Signal Processing, ASSP 31(1), 66 (1983)
Sweet, D.R.: The use of linear-time systolic algorithms for the solution of toeplitz problems. Technical Report JCU-CS-91/1, Department of Computer Science, James Cook University, January 1 (1991); Tue, 23, 15:17:55 GMT (April 1996)
Ipsen, I.: Systolic algorithms for the parallel solution of dense symmetric positive-definite Toeplitz systems. Technical Report YALEU/DCS/RR-539, Department of Computer Science, Yale University (May 1987)
Evans, D.J., Oka, G.: Parallel solution of symmetric positive definite Toeplitz systems. Parallel Algorithms and Applications 12(9), 297–303 (1998)
Gohberg, I., Koltracht, I., Averbuch, A., Shoham, B.: Timing analysis of a parallel algorithm for Toeplitz matrices on a MIMD parallel machine. Parallel Computing 17(4-5), 563–577 (1991)
Gallivan, K., Thirumalai, S., Van Dooren, P.: On solving block toeplitz systems using a block schur algorithm. In: Chandra, J. (ed.) Proceedings of the 23rd International Conference on Parallel Processing. Algorithms and Applications, vol. 3, pp. 274–281. CRC Press, Boca Raton (1994)
Thirumalai, S.: High performance algorithms to solve Toeplitz and block Toeplitz systems. Ph.d. thesis, Graduate College of the University of Illinois at Urbana-Champaign (1996)
Alonso, P., Badía, J.M., Vidal, A.M.: Parallel algorithms for the solution of toeplitz systems of linear equations. In: Proceedeings of the Fifth International Conference on Parallel Processing and Applied Mathmatics, Czestochowa, Poland. LNCS (2003) (to appear)
Anderson, E., et al.: LAPACK Users’ Guide. SIAM, Philadelphia (1995)
Blackford, L.S., et al.: ScaLAPACK Users’ Guide. SIAM, Philadelphia (1997)
Kailath, T., Sayed, A.H.: Displacement structure: Theory and applications. SIAM Review 37(3), 297–386 (1995)
Heinig, G., Bojanczyk, A.: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I. transformations. Linear Algebra and its Applications 254(1-3), 193–226 (1997)
Potts, D., Steidl, G.: Optimal trigonometric preconditioners for nonsymmetric Toeplitz systems. Linear Algebra and its Applications 281(1-3), 265–292 (1998)
Alonso, P., Badía, J.M., Vidal, A.M.: An efficient and stable parallel solution for non–symmetric Toeplitz linear systems. Technical Report II-DSIC-08/2004, Universidad Politécnica de Valencia (2004)
Swarztrauber, P.N.: Vectorizing the FFT’s. Academic Press, New York (1982)
Swarztrauber, P.N.: FFT algorithms for vector computers. Parallel Computing 1(1), 45–63 (1984)
Levinson, N.: The Wiener RMS (Root Mean Square) error criterion in filter design and prediction. Journal of Mathematics and Physics 25, 261–278 (1946)
Bitmead, R.R., Anderson, B.D.O.: Asymptotically fast solution of Toeplitz and related systems of linear equations. Linear Algebra and its Applications 34, 103–116 (1980)
Bunch, J.R.: Stability of methods for solving Toeplitz systems of equations. SIAM Journal on Scientific and Statistical Computing 6(2), 349–364 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alonso, P., Badía, J.M., Vidal, A.M. (2005). An Efficient and Stable Parallel Solution for Non-symmetric Toeplitz Linear Systems . In: Daydé, M., Dongarra, J., Hernández, V., Palma, J.M.L.M. (eds) High Performance Computing for Computational Science - VECPAR 2004. VECPAR 2004. Lecture Notes in Computer Science, vol 3402. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11403937_51
Download citation
DOI: https://doi.org/10.1007/11403937_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25424-9
Online ISBN: 978-3-540-31854-5
eBook Packages: Computer ScienceComputer Science (R0)