A truncated cyclic reduction algorithm for interval arithmetic tridiagonal systems of equations

Abstract

In many numerical problems the solution of tridiagonal systems of equations consumes an important part of the computation time. For their efficient solution on vector or parallel computers the recursive Gauss algorithm has often to be replaced by a method with a higher degree of parallelism. Among other methods cyclic reduction has been widely discussed. In the present paper we discuss some aspects of the numerical treatment of tridiagonal systems with interval coefficients which arise, for example, as part of interval arithmetic Newton-like methods combined with a “fast Poisson solver” [8, 9]. We have discussed interval arithmetic cyclic reduction in [10]. Here we introduce a truncated version dedicated to reduce the computation time. In contrast to the non-interval case we have to preserve inclusion properties. Instead of really truncating steps, we replace them by easily computable intervals. In contrast to the non-interval case we can “truncate” both the reduction and the solution phase.

Keywords:

• Interval arithmetic
• Cyclic reduction
• Tridiagonal systems
• Vector computers

C.R. Categories:

• 65H10