Search

A new block elimination method for bordered systems is proposed and its numerical properties are analysed. In the case where the leading principal block is ill-conditioned or singular and the method becomes unstable a perturbation approach is used to enhance the stability. Results of experiments performed on the SGI Power Challenge 8000 and on the Cray J-9x illustrate the performance of the new algorithm and compare it with the current best approach. It is shown that the new method works faster while preserving stability. more...

Two algorithms of the Levinson type for the solution of general Toeplitz systems are considered. The second one is better suited for vector computers while the first one is faster on scalar machines. They can break down, or behave poorly, when some of the leading principal submatrices are singular, or ill conditioned, although the whole matrix is very well conditioned. A perturbation approach is shown to work well in this case for both algorithms. The number of the additional flops can be relatively small in comparison to the look-ahead strategies. more...

Componentwise error analysis for a modification of the cyclic reduction without back substitution for a tridiagonal system is presented. We consider relative roundoff errors and equivalent perturbations, so the main supposition is that all the data is nonzero. First, backward analysis for the computation of each component of the solution in separate is presented. Bounds on the relative equivalent perturbations are obtained depending on two constants. From these bounds it is easy to obtain a componentwise forward error analysis. Then the two constants are defined for some special classes of matrices, i.e. diagonally dominant (row or column), symmetric positive definite, totally nonnegative andM-matrices, and it is shown that the bounds for these classes of matrices are small. more...

The forward stability of the block cyclic reduction without back substitution for block tridiagonal systems is studied. The basic assumption is that the matrix of the system is block column diagonally dominant. Then it is shown that for nonstrictly diagonally dominant matrices the forward error is O ( C n n 2 log 2 nκϱ 0 ), and for strictly diagonally dominant matrices it is O ( C n g ( s ) log 2 nκϱ 0 ), where n is the block size of the matrix, N is the size of each block, g ( s ) is a function which measures the diagonal dominance, κ is a condition number, and ϱ 0 is the machine roundoff unit. At the end some numerical evidence is presented. more...