\documentstyle{article} \begin{document} %\title{On the Stability of a Partitioning Algorithm %for Banded Linear Systems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % new title %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Backward Stability of a Parallel Partitioning Algorithm for Banded Linear Systems} \author{ Plamen Yalamov and Velisar Pavlov \\ Center of Applied Mathematics and Informatics, \\ University of Rousse, 7017 Rousse, Bulgaria} \begin{abstract} Banded systems of linear equations appear in many problems and are the computing time consuming kernels of various applications. It is known that the partition methods give efficient parallel algorithms for solving such systems. A typical member of the partition methods for solving tridiagonal systems is the method of Wang \cite{Wa}. Full roundoff error analysis for the whole algorithm in the case of nonsingular tridiagonal matrices is presented in \cite{siam}. In the present paper we consider the generalized partition method of Wang for nonsingular band systems, and in this case we present a full componentwise error analysis. Bounds on the equivalent perturbations are obtained depending on three constants. Then bounds on the forward error are presented as well depending on two types of condition numbers. Estimates on the first constant come directly from the roundoff error analysis of the Gaussian elimination for banded linear systems \cite{ha4}. In the present paper the second and the third constant are bounded for some special classes of matrices, i.e. row diagonally dominant, symmetric positive definite, and $M$-matrices. \end{abstract} \begin{thebibliography}{99} \bibitem{ha4} N. J. Higham, {\em Accuracy and Stability of Numerical Algorithms}, SIAM, Philadelphia, 1996. \bibitem{Wa} H.\,H.\,Wang, A parallel method for tridiagonal linear systems, {\em ACM Transactions on Mathematical Software}, 7 (1981), pp. 170--183. \bibitem{siam} P. Yalamov and V. Pavlov, Stability of a partitioning algorithm for trdiagonal systems, {\em SIAM Journal Matrix Anal. Appl.}, 1998. (to appear) \end{thebibliography} \end{document} 