[linalg.reqs]

# 29 Numerics library [[numerics]](./#numerics)

## 29.9 Basic linear algebra algorithms [[linalg]](linalg#reqs)

### 29.9.4 Requirements [linalg.reqs]

#### [29.9.4.1](#val) Linear algebra value types [[linalg.reqs.val]](linalg.reqs.val)

[1](#val-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11788)

Throughout [[linalg]](linalg "29.9 Basic linear algebra algorithms"),
the following types are[*linear algebra value types*](#def:value_type,linear_algebra "29.9.4.1 Linear algebra value types [linalg.reqs.val]"):

- [(1.1)](#val-1.1)

the value_type type alias of
any input or output mdspan parameter(s) of
any function in [[linalg]](linalg "29.9 Basic linear algebra algorithms"); and

- [(1.2)](#val-1.2)

the Scalar template parameter (if any) of
any function or class in [[linalg]](linalg "29.9 Basic linear algebra algorithms")[.](#val-1.sentence-1)

[2](#val-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11802)

Linear algebra value types shall model [semiregular](concepts.object#concept:semiregular "18.6 Object concepts [concepts.object]")[.](#val-2.sentence-1)

[3](#val-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11805)

A value-initialized object of linear algebra value type
shall act as the additive identity[.](#val-3.sentence-1)

#### [29.9.4.2](#alg) Algorithm and class requirements [[linalg.reqs.alg]](linalg.reqs.alg)

[1](#alg-1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11811)

[[linalg.reqs.alg]](#alg "29.9.4.2 Algorithm and class requirements") lists common requirements for
all algorithms and classes in [[linalg]](linalg "29.9 Basic linear algebra algorithms")[.](#alg-1.sentence-1)

[2](#alg-2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11815)

All of the following statements presume
that the algorithm's asymptotic complexity requirements, if any, are satisfied[.](#alg-2.sentence-1)

- [(2.1)](#alg-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[.](#alg-2.1.sentence-1)

- [(2.2)](#alg-2.2)

  The [*triangular solve algorithms*](#def:triangular_solve_algorithms) in[[linalg.algs.blas2.trsv]](linalg.algs.blas2.trsv "29.9.14.5 Solve a triangular linear system"),[[linalg.algs.blas3.trmm]](linalg.algs.blas3.trmm "29.9.15.3 In-place triangular matrix-matrix product"),[[linalg.algs.blas3.trsm]](linalg.algs.blas3.trsm "29.9.15.6 Solve multiple triangular linear systems"), and[[linalg.algs.blas3.inplacetrsm]](linalg.algs.blas3.inplacetrsm "29.9.15.7 Solve multiple triangular linear systems in-place") either have
a BinaryDivideOp template parameter (see [[linalg.algs.reqs]](linalg.algs.reqs "29.9.12 Algorithm requirements based on template parameter name")) and
a binary function object parameter divide of that type,
or they have effects equivalent to invoking such an algorithm[.](#alg-2.2.sentence-1)
  Triangular solve algorithms interpret divide(a, b) asa times the multiplicative inverse of b[.](#alg-2.2.sentence-2)
  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[.](#alg-2.2.sentence-3)
  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[.](#alg-2.2.sentence-4)

- [(2.3)](#alg-2.3)

  Each function in[[linalg.algs.blas1]](linalg.algs.blas1 "29.9.13 BLAS 1 algorithms"), [[linalg.algs.blas2]](linalg.algs.blas2 "29.9.14 BLAS 2 algorithms"), and [[linalg.algs.blas3]](linalg.algs.blas3 "29.9.15 BLAS 3 algorithms") 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[.](#alg-2.3.sentence-1)
  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[.](#alg-2.3.sentence-2)

- [(2.4)](#alg-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[.](#alg-2.4.sentence-1)

- [(2.5)](#alg-2.5)

  The function may reorder addends and partial sums arbitrarily[.](#alg-2.5.sentence-1)
  [*Note [1](#alg-note-1)*:
  Factors in each product are not reordered;
multiplication is not necessarily commutative[.](#alg-2.5.sentence-2)
 â *end note*]

[*Note [2](#alg-note-2)*:

The above requirements do not prohibit
implementation approaches and optimization techniques
which are not user-observable[.](#alg-2.sentence-2)

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[.](#alg-2.sentence-3)

â *end note*]

[3](#alg-3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L11896)

[*Note [3](#alg-note-3)*:

For all functions in [[linalg]](linalg "29.9 Basic linear algebra algorithms"),
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[.](#alg-3.sentence-1)

Then, functions can do all of the following:

- [(3.1)](#alg-3.1)

compute floating-point sums in any way
that improves their accuracy for arbitrary input;

- [(3.2)](#alg-3.2)

perform additional arithmetic operations
(other than those specified by the function's wording and [[linalg.reqs.alg]](#alg "29.9.4.2 Algorithm and class requirements"))
in order to improve performance or accuracy; and

- [(3.3)](#alg-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)](#alg-3.4)

the function satisfies the complexity requirements; and

- [(3.5)](#alg-3.5)

the function is logarithmically stable,
as defined in Demmel 2007[[bib]](bibliography#bib:linalg-stable "Bibliography")[.](#alg-3.sentence-2)
  Strassen's algorithm for matrix-matrix multiply
is an example of a logarithmically stable algorithm[.](#alg-3.5.sentence-2)

â *end note*]
