179 lines
7.2 KiB
Markdown
179 lines
7.2 KiB
Markdown
[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*]
|