1990 Reports

# Parametrization of Newton's iteration for computations with structured matrices and applications

We apply a new parametrized version of Newton's iteration in order to compute (over any field F of constants) the solution, or at least-squares solution, to linear system Bx = v with an n × n Toeplitz or Toeplitz-like matrix B, as well as the determinant of B and the coefficients of its characteristic polynomial, det(λI âˆ’ B), dramatically improving the processor efficiency of the known fast parallel algorithms. Our algorithms, together with some previously known and some recent results of [1““5], as well as with our new techniques for computing polynomial god's and lcm's, imply respective improvement of the known estimates for parallel arithmetic complexity of several fundamental computations with polynomials, and with both structured and general matrices.

## Subjects

## Files

- cucs-032-90.pdf application/pdf 81.7 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-032-90
- Published Here
- March 8, 2012