@article{doi:10.1137/S0097539793252687,
    Abstract = {A Las-Vegas-type probabilistic algorithm is presented for finding the Frobenius canonical form of an \$n \times n\$ matrix T over any field \$\mathfrak{K}\$. The algorithm requires \$O^{\sim}(\operatorname{MM}(n)) = \operatorname{MM}(n) \cdot (\log n)^{O(1)}\$ operations in \$\mathfrak{K}\$, where \$O(\operatorname{MM}(n))\$ operations in K are sufficient to multiply two \$n \times n\$ matrices over \$\mathfrak{K}\$. This nearly matches the lower bound of \$\Omega (\operatorname{MM}(n))\$ operations in \$\mathfrak{K}\$ for this problem and improves on the \$O(n^{4})\$ operations in \$\mathfrak{K}\$ required by the previous best-known algorithms. A fast parallel implementation of the algorithm is also demonstrated for the Frobenius form, which is processor-efficient on a PRAM. As an application we give an algorithm to evaluate a polynomial \$g \in {\mathfrak{K}}[x]\$ at T which requires only \$O^{\sim}(\operatorname{MM}(n))\$ operations in \$\mathfrak{K}\$ when \$\deg g \leq n^{2}\$. Other applications include sequential and parallel algorithms for computing the minimal and characteristic polynomials of a matrix, the rational Jordan form of a matrix (for testing whether two matrices are similar), and matrix powering, which are substantially faster than those previously known.},
    Author = {Giesbrecht, Mark},
    EPrint = {https://doi.org/10.1137/S0097539793252687},
    File = {Nearly Optimal Algorithms for Canonical Matrix Forms - s0097539793252687.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {5},
    Pages = {948-969},
    Title = {Nearly Optimal Algorithms for Canonical Matrix Forms},
    URL = {https://doi.org/10.1137/S0097539793252687},
    Volume = {24},
    Year = {1995},
    bdsk-url-1 = {https://doi.org/10.1137/S0097539793252687},
    date-added = {2023-01-30 14:25:07 +0100},
    date-modified = {2023-01-30 14:25:07 +0100},
    doi = {10.1137/S0097539793252687}
}

@article{doi:10.1137/S0097539793252687, Abstract = {A Las-Vegas-type probabilistic algorithm is presented for finding the Frobenius canonical form of an \$n \times n\$ matrix T over any field \$\mathfrak{K}\$. The algorithm requires \$O^{\sim}(\operatorname{MM}(n)) = \operatorname{MM}(n) \cdot (\log n)^{O(1)}\$ operations in \$\mathfrak{K}\$, where \$O(\operatorname{MM}(n))\$ operations in K are sufficient to multiply two \$n \times n\$ matrices over \$\mathfrak{K}\$. This nearly matches the lower bound of \$\Omega (\operatorname{MM}(n))\$ operations in \$\mathfrak{K}\$ for this problem and improves on the \$O(n^{4})\$ operations in \$\mathfrak{K}\$ required by the previous best-known algorithms. A fast parallel implementation of the algorithm is also demonstrated for the Frobenius form, which is processor-efficient on a PRAM. As an application we give an algorithm to evaluate a polynomial \$g \in {\mathfrak{K}}[x]\$ at T which requires only \$O^{\sim}(\operatorname{MM}(n))\$ operations in \$\mathfrak{K}\$ when \$\deg g \leq n^{2}\$. Other applications include sequential and parallel algorithms for computing the minimal and characteristic polynomials of a matrix, the rational Jordan form of a matrix (for testing whether two matrices are similar), and matrix powering, which are substantially faster than those previously known.}, Author = {Giesbrecht, Mark}, EPrint = {https://doi.org/10.1137/S0097539793252687}, File = {Nearly Optimal Algorithms for Canonical Matrix Forms - s0097539793252687.pdf}, Journal = {SIAM Journal on Computing}, Number = {5}, Pages = {948-969}, Title = {Nearly Optimal Algorithms for Canonical Matrix Forms}, URL = {https://doi.org/10.1137/S0097539793252687}, Volume = {24}, Year = {1995}, bdsk-url-1 = {https://doi.org/10.1137/S0097539793252687}, date-added = {2023-01-30 14:25:07 +0100}, date-modified = {2023-01-30 14:25:07 +0100}, doi = {10.1137/S0097539793252687} }