Power iteration for matrices with power series entries

Technical Summary: Power Iteration for Matrices with Power Series Entries

Problem Statement
The paper addresses the problem of finding eigenvalues and eigenvectors for matrices with entries in fields of power series, specifically the Levi-Civita field $\mathbb{C}$ and the Puiseux series field. While finding roots of polynomials over these fields is a well-studied problem in algebraic geometry and physics (e.g., Hamiltonian systems, electrical networks), solving matrix eigenvalue problems over these fields has received limited attention. Existing methods, such as calculating the roots of the characteristic polynomial, are described as computationally costly. The authors aim to adapt the classical power iteration method—a standard numerical technique for complex matrices—to these non-Archimedean fields, where standard convergence definitions do not directly apply.

Methodology and Theoretical Framework
The core of the methodology relies on the properties of the Levi-Civita field ($\mathbb{R}$ and $\mathbb{C}$), which is a non-Archimedean, Cauchy-complete, real-closed (and algebraically closed, for $\mathbb{C}$) ordered field. The authors distinguish between two types of convergence in this context:

1. Strong Convergence: Convergence with respect to the order topology.
2. Weak Convergence: Convergence of coefficients in the usual sense, which is crucial for power series representations.

The authors establish several auxiliary results regarding weak convergence, including:

• The continuity of weak convergence under addition and multiplication for "regular" sequences (sequences with left-finite support unions).
• The weak convergence of inverses ($1/a_k \to 1/a$) and square roots ($\sqrt{a_k} \to \sqrt{a}$) under specific conditions (e.g., $a[0] \neq 0$).
• A criterion for weak convergence based on the uniform convergence of coefficients on bounded subsets of the support.

The Power Iteration Algorithm
The paper proves that the power iteration method converges weakly for diagonalizable matrices over the Levi-Civita field $\mathbb{C}$ under the following conditions:

1. The matrix has at most finite entries (i.e., the valuation $\lambda(a_{ij}) \geq 0$).
2. There exists a unique eigenvalue with the strictly largest absolute value of its "complex part" (the coefficient of the $d^0$ term, denoted $\nu[0]$).
3. The initial vector has a non-zero component in the direction of the dominant eigenvector.

Specifically, if $\nu_1$ is the dominant eigenvalue such that $|\nu_1[0]| > |\nu_2[0]| \geq \dots$, the sequence of normalized vectors $x_k / \|x_k\|$ converges weakly to the normalized dominant eigenvector. Furthermore, the Rayleigh quotient $u_k^* A u_k / \|u_k\|^2$ converges weakly to the dominant eigenvalue.

To handle matrices that do not initially satisfy the "at most finite" condition or where the dominant eigenvalue is not immediately obvious, the authors propose a scaling strategy:

• Shift the matrix entries by the minimum valuation $q_0$ to create a matrix $A' = d^{-q_0}A$.
• Analyze the "complex part" matrix $\pi(A')$ (the matrix of $0$-th coefficients).
• If $\pi(A')$ has a dominated eigenvalue, the power iteration can be applied to the scaled matrix to find the dominant eigenvalue and eigenvector of the original matrix.

This approach is extended to the Puiseux series field, which is a subfield of the Levi-Civita field, allowing the method to be applied to matrices with Puiseux series entries.

Key Results

• Theorem 5.5: Establishes that if a diagonalizable matrix $A$ (possibly with infinitely large or small entries) can be scaled such that its "complex part" matrix has a strictly dominant eigenvalue, the power iteration method successfully finds the largest modulus eigenvalue and corresponding eigenvector.
• Corollary 5.7: Confirms that the method applies to diagonalizable matrices over the Puiseux series field, yielding results within the same field.
• Convergence Proofs: The paper provides rigorous proofs for the weak convergence of the vector sequence and the Rayleigh quotient, utilizing the regularity of sequences and the continuity of algebraic operations in the Levi-Civita field.

Implementation and Experimental Results
The authors implemented the algorithm in Python. They tested the method on the companion matrix of a degree-21 polynomial over the Puiseux series field $\mathbb{R}\{\{t\}\}$.

• Complexity: For companion matrices, the time complexity is estimated at $O(n d_t \log(d_t))$, where $n$ is the matrix dimension and $d_t$ is the maximum degree of the variable $t$ in the entries. For arbitrary matrices, it is $O(n^2 d_t \log(d_t))$.
• Performance: In a specific test case (degree 21 polynomial), the algorithm converged to the largest root (approximated as $100 + t + \dots$) over 100 iterations. The error decreased significantly, reaching magnitudes of $10^{-12}$ to $10^{-14}$ for most components. The execution time was approximately 135 seconds on a Lenovo p50 for 100 iterations.
• Observations: The authors note that the performance can be heavily improved with a modified version of the algorithm. They also mention implementing inverse vector iteration, subspace iteration, and the QR algorithm as complementary tools for finding remaining vectors or all vectors simultaneously.

Significance and Claims
The paper claims to provide the first power iteration algorithm specifically designed for matrices with power series entries. The authors posit that this method is not only theoretically interesting but also opens the door to developing further numerical approaches for finding roots of multivariate polynomials. They suggest these new approaches might offer better stability and efficiency compared to existing methods that rely on calculating characteristic polynomial roots. The work bridges the gap between algebraic geometry (where Puiseux series are common) and numerical linear algebra by adapting a fundamental iterative method to non-Archimedean fields.