A parallel algorithm for evaluating general linear recurrence equations (Q1922617)

This paper describes a hybrid parallel method for solving first-order linear recurrences. It uses Wang's partitioning method in a first stage, followed by cyclic reduction on the reduced system. The method is generalized to order \(n\) recurrences via transformation into a first-order recurrence in \(\mathbb{R}^n\). Numerical examples include bisection/multisection methods for the symmetric tridiagonal eigenproblem. Remark: The contents of the paper is well known to mathematicians in the field.