PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving the efficiency of a Hyperpower method for approximating inverse matrices

Alicia Cordero, Juan R. Torregrosa

arXiv:2609.04433v1math.NAcs.NA

TL;DR

High-order Hyperpower methods raise convergence order beyond Newton–Schulz but carry per-iteration matrix-product costs. This paper adapts scalar accelerators to inverse estimation, reporting sixth-order convergence with four matrix products per iteration and analyzing stability.

  • Problem

    Newton–Schulz has quadratic convergence, which can require many iterations before the residual is small.

    Source: §1 · p. 1

  • Method

    The paper adapts scalar norm-type accelerators to inverse estimation to reduce the matrix-matrix products required by the standard Hyperpower scheme.

    Source: §1 · p. 2

  • Results

    Four matrix products and two Frobenius norm calculations per iteration yield an efficiency improvement of about 16% over same-order schemes requiring at least six matrix products.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The proposed method is described as maintaining high-order convergence with less computational effort per step and as competitive for modern parallel computing environments.

    Source: §1 · p. 2

    The large-matrix efficiency analysis treats matrix-matrix products as the only cost, assuming they dominate other operations such as norm calculations.

    Source: §3 · p. 5

Abstract

from arXiv · show

In this manuscript, scalar norm-type accelerators are used for first time in order to increase the order of convergence of known iterative methods for solving the matrix equation $X^{-1}-A=0$, while decreasing the number of matrix-matrix products. Specifically, our proposed scheme upgrades the order of convergence in a $50\%$, achieving the sixth-order of convergence with the computational cost of fourth-order Hyperpower method, in terms of matrix-matrix multiplications. In the main results, not only the convergence and its order is proven, but also its efficiency and stability. This new technique provides good numerical results, even compared with existing fourth-, sixth- and eighth-order schemes in large matrices of up to $10^6$ entries, but also promises the opening of a new kind of procedures with good performance and scalability. Finally, an application to digital image restoration is made to show the behavior of the method, compared with existing ones.

1. Introduction.

The paper targets the rising per-iteration cost of high-order Hyperpower methods and introduces a scalar-accelerator approach for inverse estimation. It reports lower matrix-product cost and analyzes convergence and stability.

1. Introduction.

  • Hyperpower methods generalize Newton–Schulz to higher convergence orders to address its quadratic convergence rate and resulting large iteration counts.Newton–Schulz is described as mapping well to GPUs, while its quadratic rate can require many iterations before the residual norm is small.Source: §1 · p. 1
  • Standard Hyperpower achieves order p but requires p matrix products per iteration, so per-step cost grows with convergence order.The paper frames reducing products below the standard p-bound as a strategy for improving Ostrowski efficiency.Source: §1 · p. 2
  • The proposed method is supported by theoretical analysis and numerical experiments, and is described as competitive for modern parallel computing environments.The paper also places matrix-inverse stability analysis in a discrete-dynamics framework that studies stability intervals and starting estimates.Source: §1 · pp. 2–3
  • Scalar accelerators are adapted to inverse estimation by modifying their definition to use calculated residuals, avoiding an inverse-free formulation problem.The paper presents this as the first use of this technique for inverse matrix estimation.Source: §1 · p. 2
  • Four matrix products and two Frobenius norm calculations per iteration yield an efficiency improvement of about 16% over same-order schemes requiring at least six matrix products.The stability analysis treats the iteration as a rational operator and studies its fixed points, critical points, and basins of attraction.Source: §1 · p. 3

2. Main results.

Under a condition on the initial residual, the proposed CTM iteration converges to the inverse with sixth-order convergence. The proof establishes residual convergence and then derives the local order.

2. Main results.

  • If ∥I − AX_0∥ ≤ σ < 1, CTM converges to A^-1 with order six.The residual bound is the stated condition on the initial estimate.Source: §2 · p. 3
  • The residual tends to zero under the stated bound, so AX_k tends to I and X_k converges to A^-1.The proof uses M = 3σ^3 < 1 to bound successive residuals.Source: §2 · p. 4
  • The local-error argument establishes sixth-order convergence for the iterative scheme.The proof concludes that the method has sixth-order convergence.Source: §2 · p. 4

3. Computational Efficiency Analysis.

The proposed formulation improves the theoretical efficiency trade-off over Hyperpower schemes by reducing per-iteration matrix products. The analysis compares convergence order with computational cost and notes that matrix products dominate for large matrices.

3. Computational Efficiency Analysis.

  • The standard Hyperpower efficiency index decreases monotonically as convergence order increases.The passage attributes this decline to increasing order without optimization.Source: §3 · p. 5
  • The proposed algorithm uses four matrix-matrix products per iteration, below the standard Hyperpower requirement of p products for order p.For large matrices, matrix-matrix products dominate the computational cost; the proposal also uses two Frobenius norm calculations.Source: §3 · p. 5
  • The proposed formulation has a higher theoretical efficiency index than Hyperpower schemes, balancing convergence rate against computational effort.Figure 1 presents the efficiency indices for the proposed and known methods.Source: Figure 1 · p. 5, §3 · p. 5

4. Stability analysis.

The stability analysis models the iteration as a rational map and identifies its fixed points and attraction behavior. Its dynamical line depicts starting values that converge to the true solution or diverge.

4. Stability analysis.

  • A fixed point is strange if it is not a root; a critical point is free if it is not a root of the original function.Attracting cycles are characterized by a derivative product below one, with a zero product indicating superattraction.Source: §4 · p. 6
  • For the operator T in equation (4.1), x = 0, x = 1, and x = infinity are fixed points.The passage identifies x = 0 and x = 1 as the finite fixed points and confirms infinity as a fixed point using the auxiliary map.Source: §4 · pp. 6–7
  • The true solution x = 1 is superattracting, x = 0 repels nearby values, and x = infinity is superattracting.The derivative magnitude at zero is 6, while the inverse map has derivative zero at zero.Source: §4 · pp. 6–7
  • The analysis identifies x = 1 as a critical point and infinity as the only free critical point, concluding that iterations converge to x = 1 or diverge.The stated conclusion follows from the absence of another critical point that would create another basin of attraction.Source: §4 · p. 7
  • Figure 2 marks starting values orange if they reach x = 1 within 50 steps with error below 10^-3, and blue if they diverge toward infinity.The dynamical line uses a 500 × 500 grid, and the passage reports two basins: convergence to the solution and divergence.Source: §4 · p. 7, Figure 2 · p. 7

5. Experimental results.

The experiments compare inverse-estimation schemes on random and structured matrices, then evaluate them in a regularized image-restoration problem. CTM is reported as the fastest in several comparisons, while higher-order methods recover the image shape similarly after the iteration limit.

5. Experimental results.

  • The experiments report iteration count, final residual, and estimated convergence order; execution time is the mean of 100 runs, in seconds.The order estimate is the last stable coc value, or '-' when it does not stabilize.Source: §5 · pp. 7–8
  • CTM achieves the lowest mean convergence time on the random 300 × 300 matrix, even compared with HP8.The comparison is reported in Table 1.Source: §5 · p. 8, Table 1 · p. 8
  • On the random 1000 × 1000 matrix, CTM again has the lowest mean computational time, with small residual differences and iteration counts consistent with method order.The convergence-order estimate coc is more precise in this case.Source: §5 · p. 8, Table 2 · p. 8
  • HP8 uses the fewest iterations across the Table 3 matrices, but CTM is fastest for all; HP6 and HP8 take more CPU time, while high-order HP methods reach residuals of 10^-14.CTM matches HP6's iteration count, and NS is slowest across the tested matrices.Source: §5 · p. 9, Table 3 · p. 9

5.1. Application to digital image restoration.

  • Methods above second order recover enough of the original image shape, with no remarkable graphical differences among them.The restoration experiment uses a 200 × 200 image and regularizes the ill-conditioned blur system with Tikhonov regularization.Source: §5.1 · pp. 10, 12, Figure 4 · p. 12
  • After at most 10 iterations in image restoration, NS and HP4 have not converged, while CTM has the lowest time among converging schemes.The experiment compares last-iteration residuals and execution times.Source: §5.1 · pp. 11, 13, Table 4 · p. 13
Loading 2609.04433v1…