SOLVING SYSTEMS OF LINEAR EQUATIONS WITH QUASI-TOEPLITZ COEFFICIENT MATRICES

摘要

A matrix A is said to be quasi-Toeplitz if its entries in positions (i,j), (i - 1,j),(i,j - 1), and (i - 1,j - 1) obey a linear relation with coefficients that are independent of i and j. It is shown that a system of linear equations with a quasi-Toeplitz n × n coefficient matrix can be solved in O(n~2) arithmetic operations.