tmp/tmp9ig8dkn4/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,97 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
### Requirements <a id="linalg.reqs">[[linalg.reqs]]</a>
|
| 2 |
+
|
| 3 |
+
#### Linear algebra value types <a id="linalg.reqs.val">[[linalg.reqs.val]]</a>
|
| 4 |
+
|
| 5 |
+
Throughout [[linalg]], the following types are *linear algebra value
|
| 6 |
+
types*:
|
| 7 |
+
|
| 8 |
+
- the `value_type` type alias of any input or output `mdspan`
|
| 9 |
+
parameter(s) of any function in [[linalg]]; and
|
| 10 |
+
- the `Scalar` template parameter (if any) of any function or class in
|
| 11 |
+
[[linalg]].
|
| 12 |
+
|
| 13 |
+
Linear algebra value types shall model `semiregular`.
|
| 14 |
+
|
| 15 |
+
A value-initialized object of linear algebra value type shall act as the
|
| 16 |
+
additive identity.
|
| 17 |
+
|
| 18 |
+
#### Algorithm and class requirements <a id="linalg.reqs.alg">[[linalg.reqs.alg]]</a>
|
| 19 |
+
|
| 20 |
+
[[linalg.reqs.alg]] lists common requirements for all algorithms and
|
| 21 |
+
classes in [[linalg]].
|
| 22 |
+
|
| 23 |
+
All of the following statements presume that the algorithm’s asymptotic
|
| 24 |
+
complexity requirements, if any, are satisfied.
|
| 25 |
+
|
| 26 |
+
- The function may make arbitrarily many objects of any linear algebra
|
| 27 |
+
value type, value-initializing or direct-initializing them with any
|
| 28 |
+
existing object of that type.
|
| 29 |
+
- The *triangular solve algorithms* in [[linalg.algs.blas2.trsv]],
|
| 30 |
+
[[linalg.algs.blas3.trmm]], [[linalg.algs.blas3.trsm]], and
|
| 31 |
+
[[linalg.algs.blas3.inplacetrsm]] either have a `BinaryDivideOp`
|
| 32 |
+
template parameter (see [[linalg.algs.reqs]]) and a binary function
|
| 33 |
+
object parameter `divide` of that type, or they have effects
|
| 34 |
+
equivalent to invoking such an algorithm. Triangular solve algorithms
|
| 35 |
+
interpret `divide(a, b)` as `a` times the multiplicative inverse of
|
| 36 |
+
`b`. Each triangular solve algorithm uses a sequence of evaluations of
|
| 37 |
+
`*`, `*=`, `divide`, unary `+`, binary `+`, `+=`, unary `-`, binary
|
| 38 |
+
`-`, `-=`, and `=` operators that would produce the result specified
|
| 39 |
+
by the algorithm’s *Effects* and *Remarks* when operating on elements
|
| 40 |
+
of a field with noncommutative multiplication. It is a precondition of
|
| 41 |
+
the algorithm that any addend, any subtrahend, any partial sum of
|
| 42 |
+
addends in any order (treating any difference as a sum with the second
|
| 43 |
+
term negated), any factor, any partial product of factors respecting
|
| 44 |
+
their order, any numerator (first argument of `divide`), any
|
| 45 |
+
denominator (second argument of `divide`), and any assignment is a
|
| 46 |
+
well-formed expression.
|
| 47 |
+
- Each function in [[linalg.algs.blas1]], [[linalg.algs.blas2]], and
|
| 48 |
+
[[linalg.algs.blas3]] that is not a triangular solve algorithm will
|
| 49 |
+
use a sequence of evaluations of `*`, `*=`, `+`, `+=`, and `=`
|
| 50 |
+
operators that would produce the result specified by the algorithm’s
|
| 51 |
+
*Effects* and *Remarks* when operating on elements of a semiring with
|
| 52 |
+
noncommutative multiplication. It is a precondition of the algorithm
|
| 53 |
+
that any addend, any partial sum of addends in any order, any factor,
|
| 54 |
+
any partial product of factors respecting their order, and any
|
| 55 |
+
assignment is a well-formed expression.
|
| 56 |
+
- If the function has an output `mdspan`, then all addends, subtrahends
|
| 57 |
+
(for the triangular solve algorithms), or results of the `divide`
|
| 58 |
+
parameter on intermediate terms (if the function takes a `divide`
|
| 59 |
+
parameter) are assignable and convertible to the output `mdspan`’s
|
| 60 |
+
`value_type`.
|
| 61 |
+
- The function may reorder addends and partial sums arbitrarily.
|
| 62 |
+
\[*Note 1*: Factors in each product are not reordered; multiplication
|
| 63 |
+
is not necessarily commutative. — *end note*]
|
| 64 |
+
|
| 65 |
+
[*Note 2*: The above requirements do not prohibit implementation
|
| 66 |
+
approaches and optimization techniques which are not user-observable. In
|
| 67 |
+
particular, if for all input and output arguments the `value_type` is a
|
| 68 |
+
floating-point type, implementers are free to leverage approximations,
|
| 69 |
+
use arithmetic operations not explicitly listed above, and compute
|
| 70 |
+
floating-point sums in any way that improves their
|
| 71 |
+
accuracy. — *end note*]
|
| 72 |
+
|
| 73 |
+
[*Note 3*:
|
| 74 |
+
|
| 75 |
+
For all functions in [[linalg]], suppose that all input and output
|
| 76 |
+
`mdspan` have as `value_type` a floating-point type, and any `Scalar`
|
| 77 |
+
template argument has a floating-point type. Then, functions can do all
|
| 78 |
+
of the following:
|
| 79 |
+
|
| 80 |
+
- compute floating-point sums in any way that improves their accuracy
|
| 81 |
+
for arbitrary input;
|
| 82 |
+
- perform additional arithmetic operations (other than those specified
|
| 83 |
+
by the function’s wording and [[linalg.reqs.alg]]) in order to improve
|
| 84 |
+
performance or accuracy; and
|
| 85 |
+
- use approximations (that might not be exact even if computing with
|
| 86 |
+
real numbers), instead of computations that would be exact if it were
|
| 87 |
+
possible to compute without rounding error;
|
| 88 |
+
|
| 89 |
+
as long as
|
| 90 |
+
|
| 91 |
+
- the function satisfies the complexity requirements; and
|
| 92 |
+
- the function is logarithmically stable, as defined in Demmel 2007.
|
| 93 |
+
Strassen’s algorithm for matrix-matrix multiply is an example of a
|
| 94 |
+
logarithmically stable algorithm.
|
| 95 |
+
|
| 96 |
+
— *end note*]
|
| 97 |
+
|