Complexity bounds for solving some tridiagonal systems with preconditioning (Q1343622): Difference between revisions

The complexity of solving a linear system \(Ax = f\) is investigated for some special classes of tridiagonal matrices \(A\), when rational preconditioning on \(A\) is allowed. Nontrivial lower bounds are found and in all cases the number of necessary multiplicative operations, apart from preconditioning, is shown to be greater than the number of indeterminates defining \(A\).