The parameterized 𝑆𝑅 algorithm for symplectic (butterfly) matrices (2000)

The<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S upper R"><mml:semantics><mml:mrow><mml:mi>S</mml:mi><mml:mi>R</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">SR</mml:annotation></mml:semantics></mml:math></inline-formula>algorithm is a structure-preserving algorithm for computing the spectrum of symplectic matrices. Any symplectic matrix can be reduced to symplectic butterfly form. A symplectic matrix<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B"><mml:semantics><mml:mi>B</mml:mi><mml:annotation encoding="application/x-tex">B</mml:annotation></mml:semantics></mml:math></inline-formula>in butterfly form is uniquely determined by<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4 n minus 1"><mml:semantics><mml:mrow><mml:mn>4</mml:mn><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">4n-1</mml:annotation></mml:semantics></mml:math></inline-formula>parameters. Using these<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="4 n minus 1"><mml:semantics><mml:mrow><mml:mn>4</mml:mn><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">4n-1</mml:annotation></mml:semantics></mml:math></inline-formula>parameters, we show how one step of the symplectic<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S upper R"><mml:semantics><mml:mrow><mml:mi>S</mml:mi><mml:mi>R</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">SR</mml:annotation></mml:semantics></mml:math></inline-formula>algorithm for<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B"><mml:semantics><mml:mi>B</mml:mi><mml:annotation encoding="application/x-tex">B</mml:annotation></mml:semantics></mml:math></inline-formula>can be carried out in<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis n right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {O}(n)</mml:annotation></mml:semantics></mml:math></inline-formula>arithmetic operations compared to<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis n cubed right-parenthesis"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mn>3</mml:mn></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\mathcal {O}(n^3)</mml:annotation></mml:semantics></mml:math></inline-formula>arithmetic operations when working on the actual symplectic matrix. Moreover, the symplectic structure, which will be destroyed in the numerical process due to roundoff errors when working with a symplectic (butterfly) matrix, will be forced by working just with the parameters.