Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On the Exponent of Certain Matrix Operations
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A great deal of research was done in the period 1969–1987 on fast matrix operations, including [185, 212, 206, 213, 62]. Various proofs showed that many important matrix operations, such as QR-decomposition, LU-factorization, inversion, and finding determinants, are no more complex than matrix multiplication, in the big-Oh sense, see [13, Ch. 6] or [63, Ch. 28].
For this reason, many fast matrix multiplication algorithms were developed. Almost all were intended to work over a general ring. However, one in particular was intended for boolean matrices, and by extension
$$\mathbb{G}\mathbb{F}$$
(2)-matrices, which was named the Method of Four Russians, “after the cardinality and the nationality of its inventors.” While the Method of Four Russians was conceived as a boolean matrix multiplication tool, we show how to use it for
$$\mathbb{G}\mathbb{F}$$
(2) matrices and for inversion, in Section 9.3 on Page 137 and Section 9.4 on Page 141.