File Matrix.h

↰ Parent directory (ADS/numeric)

The product of two square matrices n x n (section 12.4):

Definition (ADS/numeric/Matrix.h)

Detailed Description

  • multiplyNaive(), :math:` c_{ij} = sum_k a_{ik} b_{kj} , :math: Theta( n^3 ) `;

  • strassen(), with A, B and C split in four blocks n / 2 x n / 2 and the seven products :math:`[ begin{array}{ll}

    X_1 = ( A_{11} + A_{22} ) ( B_{11} + B_{22} ) & X_2 = ( A_{21} + A_{22} ) B_{11} \ X_3 = A_{11} ( B_{12} - B_{22} ) & X_4 = A_{22} ( B_{21} - B_{11} ) \ X_5 = ( A_{11} + A_{12} ) B_{22} & X_6 = ( A_{21} - A_{11} ) ( B_{11} + B_{12} ) \ X_7 = ( A_{12} - A_{22} ) ( B_{21} + B_{22} ) &

    end{array}

` and :math:` C_{11} = X_1 + X_4 - X_5 + X_7 , :math: C_{12} = X_3 + X_5 , :math: C_{21} = X_2 + X_4 , :math: C_{22} = X_1 + X_3 - X_2 + X_6 : :math: T( n ) = 7 T( n / 2 ) + Theta( n^2 ) = O( n^{log_2 7} ) =

O( n^{2.81} ) `. The matrices are bordered with zeros up to a power of two, and the blocks of at most cutoff rows are multiplied by the naive method, which is faster on small ones.

Both count in *mults, if given, the products of two entries. multiply(), transpose() and scale() handle rectangular matrices.

The contracts [see File Contract.h]: the products need matrices of compatible sizes, every row as long as the first, n x n for multiplyNaive() and strassen(), p x q and q x r for multiply(), and transpose() a rectangular matrix; the result of strassen() equals the one of multiplyNaive(), an audit. The functions are defined in Matrix.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 12.4, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

  1. Strassen, Gaussian elimination is not optimal, Numerische Mathematik 13, 354-356, 1969, doi:10.1007/BF02165411

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/numeric/impl/Matrix.tpp

  • cstddef

  • vector

Included By

Namespaces

Functions

Typedefs