The Padé iterations for the matrix sign function and their reciprocals are optimal (Q649549): Difference between revisions

A common way to compute the matrix sign function is through rational iterations of the form \(z_{k+1} = \phi(z_k)\), for some rational function \(\phi(z)\) having attractive fixed points at \(1\) and \(-1\). One family of such rational functions is the \textit{Padé family of iterations}, defined as follows. Given \(z\), a variable representing a complex number, and \(\xi = 1-z^2\), we have: \[ \text{sign}(z) = \frac{z}{(z^2)^{1/2}} = \frac{z}{(1-\xi)^{1/2}} = zf(\xi), \] where \(f(\xi) = (1-\xi)^{-1/2}\). Letting \(\frac{P_{m,n}(\xi)}{Q_{m,n}(\xi)}\) be the \((m,n)\) Padé approximant to \(f(\xi)\) (\(m,n\) non-negative integers such that \(m+n\geq 1\)), the iteration \[ z_{k+1} = \frac{z_kP_{(m,n)}(1-z_k^2)}{Q_(m,n)(1-z_k^2)} =: \phi_{2m+1,2n}(z), \] where \(P_{(m,n)}(z)\) and \(Q_{(m,n)}(z)\) are polynomials of degrees \(2m+1\) and \(2n\), respectively, has been proven to be locally convergent to \(1\) and \(-1\) with order of convergence \(m+n+1\), for \(m \geq n-1\). Iterations based on the reciprocal behave similarly. Given an integer \(s>1\), and allowing non-negative integers \(m,n\) to vary over all values such that \(m+n=2s-1\), the family \(z_{k+1} = \phi_{(m,n)}(z_k)\) is the union of the Padé family and its reciprocal family. The authors prove that the functions \(\phi_{(m,n)}\) define the unique rational iterations having the lowest sum of the degrees of the numerator and the denominator among those rational iterations converging locally to \(1\) and \(-1\) with order at least \(s\). While not guaranteeing that such iterations can be evaluated with minimal cost, this property is nonetheless important for computational efficiency since, in the generic case, using Horner's scheme, the number of arithmetic operations required to evaluate \(\frac{a(z)}{b(z)}\) is directly related to the sum of the degrees of \(a\) and \(b\).