Matrix-vector product is O(n\log(n)) via fft, therefore the bandwidth of pre-conditioners could be as large as O(\log(n)) without affecting complexity. But does it need to be that large? What is the right balance between a condition number of the pre-conditioned system, overall storage, and complexity?
Matrix-vector product is O(n\log(n)) via fft, therefore the bandwidth of pre-conditioners could be as large as O(\log(n)) without affecting complexity. But does it need to be that large? What is the right balance between a condition number of the pre-conditioned system, overall storage, and complexity?