1988/01/01 by Dario A. Bini, D. Bini, Victor Y. Pan +1 · 2 citations
Computer Science · Mathematics · #Matrix Theory and Algorithms #Iterative Methods for Nonlinear Equations #Advanced Optimization Algorithms Research
paper · doi:10.1090/s0025-5718-1988-0929545-5
Let <italic>A</italic> be an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> × </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n × n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> banded block Toeplitz matrix of bandwidth <italic>k</italic> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m times m"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo> × </mml:mo> <mml:mi>m</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">m × m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> blocks having entries in a field <bold>F</bold> . We present algorithms for computing <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis lamda right-parenthesis equals det left-parenthesis upper A minus lamda upper I right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mo movablelimits="true" form="prefix">det</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>A</mml:mi> <mml:mo> − </mml:mo> <mml:mi> λ </mml:mi> <mml:mi>I</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(λ ) = det (A - λ I)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> as well as the ratio <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis lamda right-parenthesis slash p prime left-parenthesis lamda right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msup> <mml:mi>p</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(λ )/p’(λ )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p prime left-parenthesis lamda right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>p</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p’(λ )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the first derivative of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p left-parenthesis lamda right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p(λ )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with respect to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda"> <mml:semantics> <mml:mi> λ </mml:mi> <mml:annotation encoding="application/x-tex">λ</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , in roughly <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 3 slash 2 right-parenthesis k squared log n plus upper O left-parenthesis k cubed right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>3</mml:mn> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(3/2)k2log n + O(k3)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> block multiplications. If the field <bold>F</bold> supports FFT, then the cost is reduced to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis left-parenthesis m squared k log k plus m cubed k right-parenthesis log n plus k cubed m cubed right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:m