FLOP counts

Detailed Description

Theoretical floating point operation counts for linear algebra operations.

Classes
struct	batmat::linalg::flops::FlopCount
	Count of individual floating point operations, broken down by type. More...

Functions
constexpr FlopCount	batmat::linalg::flops::operator+ (FlopCount a, FlopCount b)
	Combine two flop counts by summing the counts of each operation type.
constexpr index_t	batmat::linalg::flops::total (FlopCount c)
	Compute the total number of floating point operations by summing the counts of all operation types.
constexpr FlopCount	batmat::linalg::flops::gemm (index_t m, index_t n, index_t k)
	Matrix-matrix multiplication of m×k and k×n matrices.
constexpr FlopCount	batmat::linalg::flops::trmm (index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB, MatrixStructure sC)
	Matrix-matrix multiplication of m×k and k×n matrices where one or more of the matrices are triangular or trapezoidal.
constexpr FlopCount	batmat::linalg::flops::gemmt (index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB, MatrixStructure sC)
	Matrix-matrix multiplication of m×k and k×n matrices where the result is symmetric.
constexpr FlopCount	batmat::linalg::flops::syrk (index_t n, index_t k)
	Symmetric rank-k update of n×n matrices.
constexpr FlopCount	batmat::linalg::flops::gemmt_diag (index_t m, index_t n, index_t k, MatrixStructure sC)
	Matrix-matrix multiplication of m×k and k×n matrices with a diagonal k×k matrix in the middle, where the result is symmetric.
constexpr FlopCount	batmat::linalg::flops::potrf (index_t m, index_t n)
	Cholesky factorization and triangular solve for an m×n matrix with m≥n.
constexpr FlopCount	batmat::linalg::flops::hyh_square (index_t n, index_t k)
	Hyperbolic Householder factorization update with L n×n and A nr×k.
constexpr FlopCount	batmat::linalg::flops::hyh_apply (index_t nr, index_t nc, index_t k)
	Hyperbolic Householder factorization application to L2 nr×nc and A2 nr×k.
constexpr FlopCount	batmat::linalg::flops::hyh (index_t nr, index_t nc, index_t k)
	Hyperbolic Householder factorization update with L nr×nc and A nr×k.
constexpr FlopCount	batmat::linalg::flops::syrk_potrf (index_t m, index_t n, index_t k)
	Fused symmetric rank-k update and Cholesky factorization of an m×n matrix with m≥n.
constexpr FlopCount	batmat::linalg::flops::trsm (index_t m, index_t n)
	Triangular solve of m×n matrices.
constexpr FlopCount	batmat::linalg::flops::trtri (index_t m)
	Triangular inversion of an m×m matrix.

---

Class Documentation

batmat::linalg::flops::FlopCount

struct batmat::linalg::flops::FlopCount

Class Members
index_t	fma = 0
index_t	mul = 0
index_t	add = 0
index_t	div = 0
index_t	sqrt = 0

Function Documentation

operator+()

FlopCount batmat::linalg::flops::operator+ ( FlopCount a, FlopCount b )

constexpr

#include <batmat/linalg/flops.hpp>

Combine two flop counts by summing the counts of each operation type.

Definition at line 23 of file flops.hpp.

total()

index_t batmat::linalg::flops::total ( FlopCount c )

constexpr

#include <batmat/linalg/flops.hpp>

Compute the total number of floating point operations by summing the counts of all operation types.

Definition at line 33 of file flops.hpp.

gemm()

FlopCount batmat::linalg::flops::gemm ( index_t m, index_t n, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Matrix-matrix multiplication of m×k and k×n matrices.

Implementation:

constexpr FlopCount gemm(index_t m, index_t n, index_t k) { return {.fma = m * k * n}; }

Definition at line 38 of file flops.hpp.

trmm()

FlopCount batmat::linalg::flops::trmm ( index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB, MatrixStructure sC )

constexpr

#include <batmat/linalg/flops.hpp>

Matrix-matrix multiplication of m×k and k×n matrices where one or more of the matrices are triangular or trapezoidal.

Implementation:

constexpr FlopCount trmm(index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB,
                         MatrixStructure sC) {
    using enum MatrixStructure;
    if (sB == General && sC == General) {
        if (sA == LowerTriangular || sA == UpperTriangular) { // trapezoidal A
            if (m >= k)                                       // tall A
                // x       x x x x          x x x   x x x x
                // x x     x x x x          x x x   x x x x
                // x x x   x x x x          x x x   x x x x
                // x x x                      x x
                // x x x                        x
                return {.fma = k * (k + 1) / 2 * n + (m - k) * k * n};
            else // wide A
                // x x x       x x x        x x x x x   x x x
                // x x x x     x x x          x x x x   x x x
                // x x x x x   x x x            x x x   x x x
                //             x x x                    x x x
                //             x x x                    x x x
                return {.fma = m * (m + 1) / 2 * n + (k - m) * (k - m) * n};
        } else if (sA == General) {
            return {.fma = m * k * n};
        } else {
            BATMAT_ASSUME(!"invalid structure");
        }
    } else if (sA == General && sC == General) {
        if (sB == LowerTriangular || sB == UpperTriangular) { // trapezoidal B
            if (n >= k)                                       // wide B
                return {.fma = k * (k + 1) / 2 * m + (n - k) * k * m};
            else // tall B
                return {.fma = n * (n + 1) / 2 * m + (k - n) * (k - n) * m};
        } else {
            BATMAT_ASSUME(!"invalid structure");
        }
    } else if (sA == General && sB == General) {
        if (sC == LowerTriangular || sC == UpperTriangular) {
            BATMAT_ASSUME(m == n);
            return {.fma = m * (m + 1) / 2 * k};
        } else {
            BATMAT_ASSUME(!"invalid structure");
        }
    } else if (sC == LowerTriangular || sC == UpperTriangular) {
        if (sA == transpose(sB)) {
            BATMAT_ASSUME(m == n);
            BATMAT_ASSUME(m == k);
            return {.fma = m * (m + 1) * (m + 2) / 6};
        } else {
            BATMAT_ASSUME(!"invalid structure");
        }
    } else {
        BATMAT_ASSUME(!"unsupported structure");
    }
    return {};
}

Definition at line 45 of file flops.hpp.

gemmt()

FlopCount batmat::linalg::flops::gemmt ( index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB, MatrixStructure sC )

constexpr

#include <batmat/linalg/flops.hpp>

Matrix-matrix multiplication of m×k and k×n matrices where the result is symmetric.

Implementation:

constexpr FlopCount gemmt(index_t m, index_t n, index_t k, MatrixStructure sA, MatrixStructure sB,
                          MatrixStructure sC) {
    return trmm(m, n, k, sA, sB, sC);
}

Definition at line 103 of file flops.hpp.

syrk()

FlopCount batmat::linalg::flops::syrk ( index_t n, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Symmetric rank-k update of n×n matrices.

Implementation:

constexpr FlopCount syrk(index_t n, index_t k) {
    return gemmt(n, n, k, MatrixStructure::General, MatrixStructure::General,
                 MatrixStructure::LowerTriangular);
}

Definition at line 112 of file flops.hpp.

gemmt_diag()

FlopCount batmat::linalg::flops::gemmt_diag ( index_t m, index_t n, index_t k, MatrixStructure sC )

constexpr

#include <batmat/linalg/flops.hpp>

Matrix-matrix multiplication of m×k and k×n matrices with a diagonal k×k matrix in the middle, where the result is symmetric.

Implementation:

constexpr FlopCount gemmt_diag(index_t m, index_t n, index_t k, MatrixStructure sC) {
    constexpr auto sA = MatrixStructure::General, sB = sA;
    return trmm(m, n, k, sA, sB, sC) + FlopCount{.mul = std::min(m, n) * k};
}

Definition at line 122 of file flops.hpp.

potrf()

FlopCount batmat::linalg::flops::potrf ( index_t m, index_t n )

constexpr

#include <batmat/linalg/flops.hpp>

Cholesky factorization and triangular solve for an m×n matrix with m≥n.

Implementation:

constexpr FlopCount potrf(index_t m, index_t n) {
    BATMAT_ASSUME(m >= n);
    return {
        .fma = (n + 1) * n * (n - 1) / 6    // Schur complement (square)
               + (m - n) * n * (n - 1) / 2, //                  (bottom)
        .mul = n * (n - 1) / 2              // multiplication by inverse pivot (square)
               + (m - n) * n,               //                                 (bottom)
        .div  = n,                          // inverting pivot
        .sqrt = n,                          // square root pivot
    };
}

Definition at line 131 of file flops.hpp.

hyh_square()

FlopCount batmat::linalg::flops::hyh_square ( index_t n, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Hyperbolic Householder factorization update with L n×n and A nr×k.

Implementation:

constexpr FlopCount hyh_square(index_t n, index_t k) {
    return {
        .fma  = k * n * n + 2 * n,
        .mul  = k * n + (n + 1) * n / 2 + n,
        .add  = (n + 1) * n / 2 + n,
        .div  = 2 * n,
        .sqrt = n,
    };
}

Definition at line 147 of file flops.hpp.

hyh_apply()

FlopCount batmat::linalg::flops::hyh_apply ( index_t nr, index_t nc, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Hyperbolic Householder factorization application to L2 nr×nc and A2 nr×k.

Implementation:

constexpr FlopCount hyh_apply(index_t nr, index_t nc, index_t k) {
    return {
        .fma = 2 * nr * k * nc,
        .mul = nr * nc,
        .add = nr * nc,
    };
}

Definition at line 161 of file flops.hpp.

hyh()

FlopCount batmat::linalg::flops::hyh ( index_t nr, index_t nc, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Hyperbolic Householder factorization update with L nr×nc and A nr×k.

Implementation:

constexpr FlopCount hyh(index_t nr, index_t nc, index_t k) {
    BATMAT_ASSUME(nr >= nc);
    return hyh_square(nc, k) + hyh_apply(nr - nc, nc, k);
}

Definition at line 173 of file flops.hpp.

syrk_potrf()

FlopCount batmat::linalg::flops::syrk_potrf ( index_t m, index_t n, index_t k )

constexpr

#include <batmat/linalg/flops.hpp>

Fused symmetric rank-k update and Cholesky factorization of an m×n matrix with m≥n.

Implementation:

constexpr FlopCount syrk_potrf(index_t m, index_t n, index_t k) {
    BATMAT_ASSUME(m >= n);
    return potrf(m, n) + FlopCount{.fma = n * (n + 1) * k / 2 + (m - n) * n * k};
}

Definition at line 182 of file flops.hpp.

trsm()

FlopCount batmat::linalg::flops::trsm ( index_t m, index_t n )

constexpr

#include <batmat/linalg/flops.hpp>

Triangular solve of m×n matrices.

Implementation:

constexpr FlopCount trsm(index_t m, index_t n) {
    return {.fma = m * (m - 1) * n / 2, .mul = m * n, .div = m};
}

Definition at line 191 of file flops.hpp.

trtri()

FlopCount batmat::linalg::flops::trtri ( index_t m )

constexpr

#include <batmat/linalg/flops.hpp>

Triangular inversion of an m×m matrix.

Implementation:

constexpr FlopCount trtri(index_t m) {
    return {.fma = (m + 1) * m * (m - 1) / 6, .div = m}; // TODO
}

Definition at line 199 of file flops.hpp.