A cost-efficient variant of the incremental Newton iteration for the matrix $p$th root
This work provides a more efficient algorithm for computing matrix pth roots, benefiting numerical linear algebra applications where large p values are used.
The paper presents a cost-efficient variant of the incremental Newton iteration for computing the matrix pth root, reducing computational cost from O(n^3 p) to O(n^3 log p) flops per iteration for p up to at least 100.
Incremental Newton (IN) iteration, proposed by Iannazzo, is stable for computing the matrix $p$th root, and its computational cost is $\mathcal{O}(n^3p)$ flops per iteration. In this paper, a cost-efficient variant of IN iteration is presented. The computational cost of the variant well agrees with $\mathcal{O} (n^3 \log p)$ flops per iteration, if $p$ is up to at least 100.