Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions (1993)

We consider the solution of <italic>n</italic>-by-<italic>n</italic> Toeplitz systems <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T Subscript n Baseline x equals b"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mi>x</mml:mi> <mml:mo>=</mml:mo> <mml:mi>b</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{T_n}x = b</mml:annotation> </mml:semantics> </mml:math> </inline-formula> by preconditioned conjugate gradient methods. The preconditioner <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{C_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-vertical-bar upper B Subscript n Baseline minus upper T Subscript n Baseline double-vertical-bar Subscript upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mrow> <mml:mo symmetric="true">‖</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>−<!-- − --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo symmetric="true">‖</mml:mo> </mml:mrow> <mml:mi>F</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\left \| {{B_n} - {T_n}} \right \|_F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> over all circulant matrices <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{B_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For Toeplitz matrices generated by positive <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 pi"> <mml:semantics> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>π<!-- π --></mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">2\pi</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Subscript n Superscript negative 1 Baseline upper T Subscript n"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">C_n^{ - 1}{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi>ε<!-- ε --></mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> sufficiently small, there are <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> eigenvalues of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Subscript n Superscript negative 1 Baseline upper T Subscript n"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">C_n^{ - 1}{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that lie outside the interval <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 1 minus epsilon comma 1 plus epsilon right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(1 - \varepsilon ,1 + \varepsilon )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. In particular, the spectrum of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C Subscript n Superscript negative 1 Baseline upper T Subscript n"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mi>C</mml:mi> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>T</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">C_n^{ - 1}{T_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.