28 Numerics library [numerics]

28.9 Basic linear algebra algorithms [linalg]

28.9.4 Requirements [linalg.reqs]

28.9.4.1 Linear algebra value types [linalg.reqs.val]

1
#
Throughout [linalg], the following types are linear algebra value type:
  • (1.1)
    the value_type type alias of any input or output mdspan parameter(s) of any function in [linalg]; and
  • (1.2)
    the Scalar template parameter (if any) of any function or class in [linalg].
2
#
Linear algebra value types shall model semiregular.
3
#
A value-initialized object of linear algebra value type shall act as the additive identity.

28.9.4.2 Algorithm and class requirements [linalg.reqs.alg]

1
#
[linalg.reqs.alg] lists common requirements for all algorithms and classes in [linalg].
2
#
All of the following statements presume that the algorithm's asymptotic complexity requirements, if any, are satisfied.
  • (2.1)
    The function may make arbitrarily many objects of any linear algebra value type, value-initializing or direct-initializing them with any existing object of that type.
  • (2.2)
    The triangular solve algorithms in [linalg.algs.blas2.trsv], [linalg.algs.blas3.trmm], [linalg.algs.blas3.trsm], and [linalg.algs.blas3.inplacetrsm] either have a BinaryDivideOp template parameter (see [linalg.algs.reqs]) and a binary function object parameter divide of that type, or they have effects equivalent to invoking such an algorithm.
    Triangular solve algorithms interpret divide(a, b) as a times the multiplicative inverse of b.
    Each triangular solve algorithm uses a sequence of evaluations of *, *=, divide, unary +, binary +, +=, unary -, binary -, -=, and = operators that would produce the result specified by the algorithm's Effects and Remarks when operating on elements of a field with noncommutative multiplication.
    It is a precondition of the algorithm that any addend, any subtrahend, any partial sum of addends in any order (treating any difference as a sum with the second term negated), any factor, any partial product of factors respecting their order, any numerator (first argument of divide), any denominator (second argument of divide), and any assignment is a well-formed expression.
  • (2.3)
    Each function in [linalg.algs.blas1], [linalg.algs.blas2], and [linalg.algs.blas3] that is not a triangular solve algorithm will use a sequence of evaluations of *, *=, +, +=, and = operators that would produce the result specified by the algorithm's Effects and Remarks when operating on elements of a semiring with noncommutative multiplication.
    It is a precondition of the algorithm that any addend, any partial sum of addends in any order, any factor, any partial product of factors respecting their order, and any assignment is a well-formed expression.
  • (2.4)
    If the function has an output mdspan, then all addends, subtrahends (for the triangular solve algorithms), or results of the divide parameter on intermediate terms (if the function takes a divide parameter) are assignable and convertible to the output mdspan's value_type.
  • (2.5)
    The function may reorder addends and partial sums arbitrarily.
    [Note 1: 
    Factors in each product are not reordered; multiplication is not necessarily commutative.
    — end note]
[Note 2: 
The above requirements do not prohibit implementation approaches and optimization techniques which are not user-observable.
In particular, if for all input and output arguments the value_type is a floating-point type, implementers are free to leverage approximations, use arithmetic operations not explicitly listed above, and compute floating point sums in any way that improves their accuracy.
— end note]
3
#
[Note 3: 
For all functions in [linalg], suppose that all input and output mdspan have as value_type a floating-point type, and any Scalar template argument has a floating-point type.
Then, functions can do all of the following:
  • (3.1)
    compute floating-point sums in any way that improves their accuracy for arbitrary input;
  • (3.2)
    perform additional arithmetic operations (other than those specified by the function's wording and [linalg.reqs.alg]) in order to improve performance or accuracy; and
  • (3.3)
    use approximations (that might not be exact even if computing with real numbers), instead of computations that would be exact if it were possible to compute without rounding error;
as long as
  • (3.4)
    the function satisfies the complexity requirements; and
  • (3.5)
    the function is logarithmically stable, as defined in Demmel 2007[bib].
    Strassen's algorithm for matrix-matrix multiply is an example of a logarithmically stable algorithm.
— end note]