Wrap around partitioning for block bidiagonal linear systems

Research Report MRR96-018

Wrap around partitioning for block bidiagonal linear systems

Markus Hegland and M. R. Osborne

Abstract: Wrap-around partitioning is a reordering of the variables in a system of linear equations into q blocks of p variables each. This permits sets of variables that can be eliminated independently to be highlighted, and provides a basis for effective vectorization over the p indices within each block of the solution process. For block bidiagonal systems the result of eliminating variables in the first q-1 blocks is a final block of dimension $\geq p$ (an exact partitioning of all the variables at each stage is not assumed) which is again in block bidiagonal form provided either Gaussian elimination with partial pivoting or orthogonal factorization is used. Thus the transformation can be applied recursively, with the only limitation being a practical one implied by the value of $n_{1/2}$ . Optimum choice of the sizes of the recursively defined transformations is considered under the standard model of vector computation. It is shown that a strategy related to cyclic reduction is likely to be effective for large enough linear systems when power of 2 stride access to memory is not restricted by the machine architecture. Otherwise, a power of 3 stride access pattern can be used.

Select this link for a text-only version of this abstract.

This service is maintained by the Mathematical Sciences Institute (MSI)
Comments to webmaster@maths.anu.edu.au URL: http://wwwmaths.anu.edu.au/