Some special classes of tridiagonal matrices A are considered, and the complexity of solving a linear system Ax = f is investigated, when rational
preconditioning on A is allowed. Non-trivial 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.
