Linearly connected arrays for Toeplitz least-squares problems
Adam W. Bojańczyk, Richard P. Brent, Frank Robert De Hoog · Journal of Parallel and Distributed Computing · 1990
We present a linearly connected array of O(n) cells that solves the linear least-squares problem for an (m + 1) × (n + 1) Toeplitz matrix in time O(m + n). The total storage required is O(n) words, i.e., only a constant per cell. The parallel algorithm described in this paper is based on the sequential QR factorization algorithm for Toeplitz matrices recently developed by the authors.