P1673R7
A free function linear algebra interface based on the BLAS

Published Proposal,

This version:
https://github.com/ORNL/cpp-proposals-pub/blob/master/D1673/P1673.bs
Author:
(NVIDIA)
Project:
ISO/IEC JTC1/SC22/WG21 14882: Programming Language — C++

Abstract

We propose a C++ Standard Library dense linear algebra interface based on the dense Basic Linear Algebra Subroutines (BLAS). This corresponds to a subset of the BLAS Standard.

1. Authors and contributors

1.1. Authors

1.2. Contributors

2. Revision history

3. Purpose of this paper

This paper proposes a C++ Standard Library dense linear algebra interface based on the dense Basic Linear Algebra Subroutines (BLAS). This corresponds to a subset of the BLAS Standard. Our proposal implements the following classes of algorithms on arrays that represent matrices and vectors:

Our algorithms work with most of the matrix storage formats that the BLAS Standard supports:

Our proposal also has the following distinctive characteristics:

Here are some examples of what this proposal offers. In these examples, we ignore std:: namespace qualification for anything in our proposal or for mdspan. We start with a "hello world" that scales the elements of a 1-D mdspan by a constant factor, first sequentially, then in parallel.

  constexpr size_t N = 40;
  std::vector<double> x_vec(N);

  mdspan x(x_vec.data(), N);
  for(size_t i = 0; i < N; ++i) {
    x[i] = double(i);
    y[i] = double(i) + 1.0;
  }

  linalg::scale(2.0, x); // x = 2.0 * x
  linalg::scale(std::execution::par_unseq, 3.0, x);
  for(size_t i = 0; i < N; ++i) {
    assert(x[i] == 6.0 * double(i));
  }

Here is a matrix-vector product example. It illustrates the scaled function that makes our interface more concise, while still permitting the BLAS' performance optimization of fusing computations with multiplications by a scalar. It also shows the ability to exploit dimensions known at compile time, and to mix compile-time and run-time dimensions arbitrarily.

constexpr size_t N = 40;
constexpr size_t M = 20;

std::vector<double> A_vec(N*M);
std::vector<double> x_vec(M);
std::array<double, N> y_vec(N);

mdspan A(A_vec.data(), N, M);
mdspan x(x_vec.data(), M);
mdspan<double, extents<N>> y(y_vec.data());

for(int i = 0; i < A.extent(0); ++i) {
  for(int j = 0; j < A.extent(1); ++j) {
    A[i,j] = 100.0 * i + j;
  }
}
for(int j = 0; j < x.extent(0); ++j) {
  x[i] = 1.0 * j;
}
for(int i = 0; i < y.extent(0); ++i) {
  y[i] = -1.0 * i;
}

linalg::matrix_vector_product(A, x, y); // y = A * x

// y = 0.5 * y + 2 * A * x
linalg::matrix_vector_product(std::execution::par,
  linalg::scaled(2.0, A), x,
  linalg::scaled(0.5, y), y);

This example illustrates the ability to perform mixed-precision computations, and the ability to compute on subviews of a matrix or vector by using submdspan.

constexpr size_t M = 40;

std::vector<float> A_vec(M*8*4);
std::vector<double> x_vec(M*4);
std::vector<double> y_vec(M*8);

mdspan<float, extents<dynamic_extent, 8, 4>> A(A_vec.data(), M);
mdspan<double, extents<4, dynamic_extent>> x(x_vec.data(), M);
mdspan<double, extents<dynamic_extent, 8>> y(y_vec.data(), M);

for(size_t m = 0; m < A.extent(0); ++m) {
  for(size_t i = 0; i < A.extent(1); ++i) {
    for(size_t j = 0; j < A.extent(2); ++j) {
      A[m,i,j] = 1000.0 * m + 100.0 * i + j;
    }
  }
}
for(size_t i = 0; i < x.extent(0); ++i) {
  for(size_t m = 0; m < x.extent(1); ++m) {
    x[i,m] = 33. * i + 0.33 * m;
  }
}
for(size_t m = 0; m < y.extent(0); ++m) {
  for(size_t i = 0; i < y.extent(1); ++i) {
    y[m,i] = 33. * m + 0.33 * i;
  }
}

for(size_t m = 0; m < M; ++m) {
  auto A_m = submdspan(A, m, full_extent, full_extent);
  auto x_m = submdspan(x, full_extent, m);
  auto y_m = submdspan(y, m, full_extent);
  // y_m = A * x_m
  linalg::matrix_vector_product(A_m, x_m, y_m);
}

4. Overview of contents

Section 5 explains how this proposal is interoperable with other linear algebra proposals currently under WG21 review. In particular, we believe this proposal is complementary to P1385R6, and the authors of P1385R6 have expressed the same view.

Section 6 motivates considering any dense linear algebra proposal for the C++ Standard Library.

Section 7 shows why we chose the BLAS as a starting point for our proposed library. The BLAS is an existing standard with decades of use, a rich set of functions, and many optimized implementations.

Section 8 lists what we consider general criteria for including algorithms in the C++ Standard Library. We rely on these criteria to justify the algorithms in this proposal.

Section 9 describes BLAS notation and conventions in C++ terms. Understanding this will give readers context for algorithms, and show how our proposed algorithms expand on BLAS functionality.

Section 10 lists functionality that we intentionally exclude from our proposal. We imitate the BLAS in aiming to be a set of "performance primitives" on which external libraries or applications may build a more complete linear algebra solution.

Section 11 elaborates on our design justification. This section explains

Section 12 lists future work, that is, ways future proposals could build on this one.

Section 13 gives the data structures and utilities from other proposals on which we depend. In particular, we rely heavily on mdspan (P0009), and add custom layouts and accessors.

Section 14 credits funding agencies and contributors.

Section 15 is our bibliography.

Section 16 is where readers will find the normative wording we propose.

Finally, Section 17 gives some more elaborate examples of linear algebra algorithms that use our proposal. The examples show how mdspan's features let users easily describe "submatrices" with submdspan. This integrates naturally with "block" factorizations of matrices. The resulting notation is concise, yet still computes in place, without unnecessary copies of any part of the matrix.

Here is a table that maps between Reference BLAS function name, and algorithm or function name in our proposal. The mapping is not always one to one. "N/A" in the "BLAS name(s)" field means that the function is not in the BLAS.

BLAS name(s) Our name(s)
xLARTG givens_rotation_setup
xROT givens_rotation_apply
xSWAP swap_elements
xSCAL scale, scaled
xCOPY copy
xAXPY add, scaled
xDOT, xDOTU dot
xDOTC dotc
N/A vector_sum_of_squares
xNRM2 vector_norm2
xASUM vector_abs_sum
xIAMAX idx_abs_max
N/A matrix_frob_norm
N/A matrix_one_norm
N/A matrix_inf_norm
xGEMV matrix_vector_product
xSYMV symmetric_matrix_vector_product
xHEMV hermitian_matrix_vector_product
xTRMV triangular_matrix_vector_product
xTRSV triangular_matrix_vector_solve
xGER, xGERU matrix_rank_1_update
xGERC matrix_rank_1_update_c
xSYR symmetric_matrix_rank_1_update
xHER hermitian_matrix_rank_1_update
xSYR2 symmetric_matrix_rank_2_update
xHER2 hermitian_matrix_rank_2_update
xGEMM matrix_product
xSYMM symmetric_matrix_{left,right}_product
xHEMM hermitian_matrix_{left,right}_product
xTRMM triangular_matrix_{left,right}_product
xSYRK symmetric_matrix_rank_k_update
xHERK hermitian_matrix_rank_k_update
xSYR2K symmetric_matrix_rank_2k_update
xHER2K hermitian_matrix_rank_2k_update
xTRSM triangular_matrix_matrix_{left,right}_solve

5. Interoperable with other linear algebra proposals

We believe this proposal is complementary to P1385R6, a proposal for a C++ Standard linear algebra library that introduces matrix and vector classes with overloaded arithmetic operators. The P1385 authors and we have expressed together in a joint paper, P1891, that P1673 and P1385 "are orthogonal. They are not competing papers; ... there is no overlap of functionality."

Many of us have had experience using and implementing matrix and vector operator arithmetic libraries like what P1385 proposes. We designed P1673 in part as a natural foundation or implementation layer for such libraries. Our view is that a free function interface like P1673’s clearly separates algorithms from data structures, and more naturally allows for a richer set of operations such as what the BLAS provides. Our paper P1674 explains why we think our proposal is a minimal C++ "respelling" of the BLAS.

A natural extension of the present proposal would include accepting P1385’s matrix and vector objects as input for the algorithms proposed here. A straightforward way to do that would be for P1385’s matrix and vector objects to make views of their data available as mdspan.

6. Why include dense linear algebra in the C++ Standard Library?

  1. "Direction for ISO C++" (P0939R4) explicitly calls out "Linear Algebra" as a potential priority for C++23.

  2. C++ applications in "important application areas" (see P0939R4) have depended on linear algebra for a long time.

  3. Linear algebra is like sort: obvious algorithms are slow, and the fastest implementations call for hardware-specific tuning.

  4. Dense linear algebra is core functionality for most of linear algebra, and can also serve as a building block for tensor operations.

  5. The C++ Standard Library includes plenty of "mathematical functions." Linear algebra operations like matrix-matrix multiply are at least as broadly useful.

  6. The set of linear algebra operations in this proposal are derived from a well-established, standard set of algorithms that has changed very little in decades. It is one of the strongest possible examples of standardizing existing practice that anyone could bring to C++.

  7. This proposal follows in the footsteps of many recent successful incorporations of existing standards into C++, including the UTC and TAI standard definitions from the International Telecommunications Union, the time zone database standard from the International Assigned Numbers Authority, and the ongoing effort to integrate the ISO unicode standard.

Linear algebra has had wide use in C++ applications for nearly three decades (see P1417R0 for a historical survey). For much of that time, many third-party C++ libraries for linear algebra have been available. Many different subject areas depend on linear algebra, including machine learning, data mining, web search, statistics, computer graphics, medical imaging, geolocation and mapping, engineering, and physics-based simulations.

"Directions for ISO C++" (P0939R4) not only lists "Linear Algebra" explicitly as a potential C++23 priority, it also offers the following in support of adding linear algebra to the C++ Standard Library.

Obvious algorithms for some linear algebra operations like dense matrix-matrix multiply are asymptotically slower than less-obvious algorithms. (Please refer to a survey one of us coauthored, "Communication lower bounds and optimal algorithms for numerical linear algebra.") Furthermore, writing the fastest dense matrix-matrix multiply depends on details of a specific computer architecture. This makes such operations comparable to sort in the C++ Standard Library: worth standardizing, so that Standard Library implementers can get them right and hardware vendors can optimize them. In fact, almost all C++ linear algebra libraries end up calling non-C++ implementations of these algorithms, especially the implementations in optimized BLAS libraries (see below). In this respect, linear algebra is also analogous to standard library features like random_device: often implemented directly in assembly or even with special hardware, and thus an essential component of allowing no room for another language "below" C++ (see P0939R4) and Stroustrup’s "The Design and Evolution of C++").

Dense linear algebra is the core component of most algorithms and applications that use linear algebra, and the component that is most widely shared over different application areas. For example, tensor computations end up spending most of their time in optimized dense linear algebra functions. Sparse matrix computations get best performance when they spend as much time as possible in dense linear algebra.

The C++ Standard Library includes many "mathematical special functions" ([sf.cmath]), like incomplete elliptic integrals, Bessel functions, and other polynomials and functions named after various mathematicians. Any of them comes with its own theory and set of applications for which robust and accurate implementations are indispensible. We think that linear algebra operations are at least as broadly useful, and in many cases significantly more so.

7. Why base a C++ linear algebra library on the BLAS?

  1. The BLAS is a standard that codifies decades of existing practice.

  2. The BLAS separates "performance primitives" for hardware experts to tune, from mathematical operations that rely on those primitives for good performance.

  3. Benchmarks reward hardware and system vendors for providing optimized BLAS implementations.

  4. Writing a fast BLAS implementation for common element types is nontrivial, but well understood.

  5. Optimized third-party BLAS implementations with liberal software licenses exist.

  6. Building a C++ interface on top of the BLAS is a straightforward exercise, but has pitfalls for unaware developers.

Linear algebra has had a cross-language standard, the Basic Linear Algebra Subroutines (BLAS), since 2002. The Standard came out of a standardization process that started in 1995 and held meetings three times a year until 1999. Participants in the process came from industry, academia, and government research laboratories. The dense linear algebra subset of the BLAS codifies forty years of evolving practice, and has existed in recognizable form since 1990 (see P1417R0).

The BLAS interface was specifically designed as the distillation of the "computer science" / performance-oriented parts of linear algebra algorithms. It cleanly separates operations most critical for performance, from operations whose implementation takes expertise in mathematics and rounding-error analysis. This gives vendors opportunities to add value, without asking for expertise outside the typical required skill set of a Standard Library implementer.

Well-established benchmarks such as the LINPACK benchmark reward computer hardware vendors for optimizing their BLAS implementations. Thus, many vendors provide an optimized BLAS library for their computer architectures. Writing fast BLAS-like operations is not trivial, and depends on computer architecture. However, it is a well-understood problem whose solutions could be parameterized for a variety of computer architectures. See, for example, Goto and van de Geijn 2008. There are optimized third-party BLAS implementations for common architectures, like ATLAS and GotoBLAS. A (slow but correct) reference implementation of the BLAS exists and it has a liberal software license for easy reuse.

We have experience in the exercise of wrapping a C or Fortran BLAS implementation for use in portable C++ libraries. We describe this exercise in detail in our paper "Evolving a Standard C++ Linear Algebra Library from the BLAS" (P1674R1). It is straightforward for vendors, but has pitfalls for developers. For example, Fortran’s application binary interface (ABI) differs across platforms in ways that can cause run-time errors (even incorrect results, not just crashing). Historical examples of vendors' C BLAS implementations have also had ABI issues that required work-arounds. This dependence on ABI details makes availability in a standard C++ library valuable.

8. Criteria for including algorithms

We include algorithms in our proposal based on the following criteria, ordered by decreasing importance. Many of our algorithms satisfy multiple criteria.

  1. Getting the desired asymptotic run time is nontrivial

  2. Opportunity for vendors to provide hardware-specific optimizations

  3. Opportunity for vendors to provide quality-of-implementation improvements, especially relating to accuracy or reproducibility with respect to floating-point rounding error

  4. User convenience (familiar name, or tedious to implement)

Regarding (1), "nontrivial" means "at least for novices to the field." Dense matrix-matrix multiply is a good example. Getting close to the asymptotic lower bound on the number of memory reads and writes matters a lot for performance, and calls for a nonintuitive loop reordering. An analogy to the current C++ Standard Library is sort, where intuitive algorithms that many humans use are not asymptotically optimal.

Regarding (2), a good example is copying multidimensional arrays. The Kokkos library spends about 2500 lines of code on multidimensional array copy, yet still relies on system libraries for low-level optimizations. An analogy to the current C++ Standard Library is copy or even memcpy.

Regarding (3), accurate floating-point summation is nontrivial. Well-meaning compiler optimizations might defeat even simple technqiues, like compensated summation. The most obvious way to compute a vector’s Euclidean norm (square root of sum of squares) can cause overflow or underflow, even when the exact answer is much smaller than the overflow threshold, or larger than the underflow threshold. Some users care deeply about sums, even parallel sums, that always get the same answer, despite rounding error. This can help debugging, for example. It is possible to make floating-point sums completely independent of parallel evaluation order. See e.g., the ReproBLAS effort. Naming these algorithms and providing ExecutionPolicy customization hooks gives vendors a chance to provide these improvements. An analogy to the current C++ Standard Library is hypot, whose language in the C++ Standard alludes to the tighter POSIX requirements.

Regarding (4), the C++ Standard Library is not entirely minimalist. One example is std::string::contains. Existing Standard Library algorithms already offered this functionality, but a member contains function is easy for novices to find and use, and avoids the tedium of comparing the result of find to npos.

The BLAS exists mainly for the first two reasons. It includes functions that were nontrivial for compilers to optimize in its time, like scaled elementwise vector sums, as well as functions that generally require human effort to optimize, like matrix-matrix multiply.

9. Notation and conventions

9.1. The BLAS uses Fortran terms

The BLAS' "native" language is Fortran. It has a C binding as well, but the BLAS Standard and documentation use Fortran terms. Where applicable, we will call out relevant Fortran terms and highlight possibly confusing differences with corresponding C++ ideas. Our paper P1674 ("Evolving a Standard C++ Linear Algebra Library from the BLAS") goes into more detail on these issues.

9.2. We call "subroutines" functions

Like Fortran, the BLAS distinguishes between functions that return a value, and subroutines that do not return a value. In what follows, we will refer to both as "BLAS functions" or "functions."

9.3. Element types and BLAS function name prefix

The BLAS implements functionality for four different matrix, vector, or scalar element types:

The BLAS' Fortran 77 binding uses a function name prefix to distinguish functions based on element type:

For example, the four BLAS functions SAXPY, DAXPY, CAXPY, and ZAXPY all perform the vector update Y = Y + ALPHA*X for vectors X and Y and scalar ALPHA, but for different vector and scalar element types.

The convention is to refer to all of these functions together as xAXPY. In general, a lower-case x is a placeholder for all data type prefixes that the BLAS provides. For most functions, the x is a prefix, but for a few functions like IxAMAX, the data type "prefix" is not the first letter of the function name. (IxAMAX is a Fortran function that returns INTEGER, and therefore follows the old Fortran implicit naming rule that integers start with I, J, etc.)

Not all BLAS functions exist for all four data types. These come in three categories:

  1. The BLAS provides only real-arithmetic (S and D) versions of the function, since the function only makes mathematical sense in real arithmetic.

  2. The complex-arithmetic versions perform a slightly different mathematical operation than the real-arithmetic versions, so they have a different base name.

  3. The complex-arithmetic versions offer a choice between nonconjugated or conjugated operations.

As an example of the second category, the BLAS functions SASUM and DASUM compute the sums of absolute values of a vector’s elements. Their complex counterparts CSASUM and DZASUM compute the sums of absolute values of real and imaginary components of a vector v, that is, the sum of abs(real(v[i])) + abs(imag(v[i])) for all i in the domain of v. The latter operation is still useful as a vector norm, but it requires fewer arithmetic operations.

Examples of the third category include the following:

The conjugate transpose and the (nonconjugated) transpose are the same operation in real arithmetic (if one considers real arithmetic embedded in complex arithmetic), but differ in complex arithmetic. Different applications have different reasons to want either. The C++ Standard includes complex numbers, so a Standard linear algebra library needs to respect the mathematical structures that go along with complex numbers.

10. What we exclude from the design

10.1. Most functions not in the Reference BLAS

The BLAS Standard includes functionality that appears neither in the Reference BLAS library, nor in the classic BLAS "level" 1, 2, and 3 papers. (For history of the BLAS "levels" and a bibliography, see P1417R0. For a paper describing functions not in the Reference BLAS, see "An updated set of basic linear algebra subprograms (BLAS)," listed in "Other references" below.) For example, the BLAS Standard has

Our proposal only includes core Reference BLAS functionality, for the following reasons:

  1. Vendors who implement a new component of the C++ Standard Library will want to see and test against an existing reference implementation.

  2. Many applications that use sparse linear algebra also use dense, but not vice versa.

  3. The Sparse BLAS interface is a stateful interface that is not consistent with the dense BLAS, and would need more extensive redesign to translate into a modern C++ idiom. See discussion in P1417R0.

  4. Our proposal subsumes some dense mixed-precision functionality (see below).

We have included vector sum-of-squares and matrix norms as exceptions, for the same reason that we include vector 2-norm: to expose hooks for quality-of-implementation improvements that avoid underflow or overflow when computing with floating-point values.

The LAPACK Fortran library implements solvers for the following classes of mathematical problems:

It also provides matrix factorizations and related linear algebra operations. LAPACK deliberately relies on the BLAS for good performance; in fact, LAPACK and the BLAS were designed together. See history presented in P1417R0.

Several C++ libraries provide slices of LAPACK functionality. Here is a brief, noninclusive list, in alphabetical order, of some libraries actively being maintained:

P1417R0 gives some history of C++ linear algebra libraries. The authors of this proposal have designed, written, and maintained LAPACK wrappers in C++. Some authors have LAPACK founders as PhD advisors. Nevertheless, we have excluded LAPACK-like functionality from this proposal, for the following reasons:

  1. LAPACK is a Fortran library, unlike the BLAS, which is a multilanguage standard.

  2. We intend to support more general element types, beyond the four that LAPACK supports. It’s much more straightforward to make a C++ BLAS work for general element types, than to make LAPACK algorithms work generically.

First, unlike the BLAS, LAPACK is a Fortran library, not a standard. LAPACK was developed concurrently with the "level 3" BLAS functions, and the two projects share contributors. Nevertheless, only the BLAS and not LAPACK got standardized. Some vendors supply LAPACK implementations with some optimized functions, but most implementations likely depend heavily on "reference" LAPACK. There have been a few efforts by LAPACK contributors to develop C++ LAPACK bindings, from Lapack++ in pre-templates C++ circa 1993, to the recent "C++ API for BLAS and LAPACK". (The latter shares coauthors with this proposal.) However, these are still just C++ bindings to a Fortran library. This means that if vendors had to supply C++ functionality equivalent to LAPACK, they would either need to start with a Fortran compiler, or would need to invest a lot of effort in a C++ reimplementation. Mechanical translation from Fortran to C++ introduces risk, because many LAPACK functions depend critically on details of floating-point arithmetic behavior.

Second, we intend to permit use of matrix or vector element types other than just the four types that the BLAS and LAPACK support. This includes "short" floating-point types, fixed-point types, integers, and user-defined arithmetic types. Doing this is easier for BLAS-like operations than for the much more complicated numerical algorithms in LAPACK. LAPACK strives for a "generic" design (see Jack Dongarra interview summary in P1417R0), but only supports two real floating-point types and two complex floating-point types. Directly translating LAPACK source code into a "generic" version could lead to pitfalls. Many LAPACK algorithms only make sense for number systems that aim to approximate real numbers (or their complex extentions). Some LAPACK functions output error bounds that rely on properties of floating-point arithmetic.

For these reasons, we have left LAPACK-like functionality for future work. It would be natural for a future LAPACK-like C++ library to build on our proposal.

10.3. Extended-precision BLAS

Our interface subsumes some functionality of the Mixed-Precision BLAS specification (Chapter 4 of the BLAS Standard). For example, users may multiply two 16-bit floating-point matrices (assuming that a 16-bit floating-point type exists) and accumulate into a 32-bit floating-point matrix, just by providing a 32-bit floating-point matrix as output. Users may specify the precision of a dot product result. If it is greater than the input vectors' element type precisions (e.g., double vs. float), then this effectively performs accumulation in higher precision. Our proposal imposes semantic requirements on some functions, like vector_norm2, to behave in this way.

However, we do not include the "Extended-Precision BLAS" in this proposal. The BLAS Standard lets callers decide at run time whether to use extended precision floating-point arithmetic for internal evaluations. We could support this feature at a later time. Implementations of our interface also have the freedom to use more accurate evaluation methods than typical BLAS implementations. For example, it is possible to make floating-point sums completely independent of parallel evaluation order.

10.4. Arithmetic operators and associated expression templates

Our proposal omits arithmetic operators on matrices and vectors. We do so for the following reasons:

  1. We propose a low-level, minimal interface.

  2. operator* could have multiple meanings for matrices and vectors. Should it mean elementwise product (like valarray) or matrix product? Should libraries reinterpret "vector times vector" as a dot product (row vector times column vector)? We prefer to let a higher-level library decide this, and make everything explicit at our lower level.

  3. Arithmetic operators require defining the element type of the vector or matrix returned by an expression. Functions let users specify this explicitly, and even let users use different output types for the same input types in different expressions.

  4. Arithmetic operators may require allocation of temporary matrix or vector storage. This prevents use of nonowning data structures.

  5. Arithmetic operators strongly suggest expression templates. These introduce problems such as dangling references and aliasing.

Our goal is to propose a low-level interface. Other libraries, such as that proposed by P1385R6, could use our interface to implement overloaded arithmetic for matrices and vectors. A constrained, function-based, BLAS-like interface builds incrementally on the many years of BLAS experience.

Arithmetic operators on matrices and vectors would require the library, not necessarily the user, to specify the element type of an expression’s result. This gets tricky if the terms have mixed element types. For example, what should the element type of the result of the vector sum x + y be, if x has element type complex<float> and y has element type double? It’s tempting to use common_type_t, but common_type_t<complex<float>, double> is complex<float>. This loses precision. Some users may want complex<double>; others may want complex<long double> or something else, and others may want to choose different types in the same program.

P1385R6 lets users customize the return type of such arithmetic expressions. However, different algorithms may call for the same expression with the same inputs to have different output types. For example, iterative refinement of linear systems Ax=b can work either with an extended-precision intermediate residual vector r = b - A*x, or with a residual vector that has the same precision as the input linear system. Each choice produces a different algorithm with different convergence characteristics, per-iteration run time, and memory requirements. Thus, our library lets users specify the result element type of linear algebra operations explicitly, by calling a named function that takes an output argument explicitly, rather than an arithmetic operator.

Arithmetic operators on matrices or vectors may also need to allocate temporary storage. Users may not want that. When LAPACK’s developers switched from Fortran 77 to a subset of Fortran 90, their users rejected the option of letting LAPACK functions allocate temporary storage on their own. Users wanted to control memory allocation. Also, allocating storage precludes use of nonowning input data structures like mdspan, that do not know how to allocate.

Arithmetic expressions on matrices or vectors strongly suggest expression templates, as a way to avoid allocation of temporaries and to fuse computational kernels. They do not require expression templates. For example, valarray offers overloaded operators for vector arithmetic, but the Standard lets implementers decide whether to use expression templates. However, all of the current C++ linear algebra libraries that we mentioned above have some form of expression templates for overloaded arithmetic operators, so users will expect this and rely on it for good performance. This was, indeed, one of the major complaints about initial implementations of valarray: its lack of mandate for expression templates meant that initial implementations were slow, and thus users did not want to rely on it. (See Josuttis 1999, p. 547, and Vandevoorde and Josuttis 2003, p. 342, for a summary of the history. Fortran has an analogous issue, in which (under certain conditions) it is implementation defined whether the run-time environment needs to copy noncontiguous slices of an array into contiguous temporary storage.)

Expression templates work well, but have issues. Our papers P1417R0 and "Evolving a Standard C++ Linear Algebra Library from the BLAS" (P1674R1) give more detail on these concerns. A particularly troublesome one is that C++ auto type deduction makes it easy for users to capture expressions before the expression templates system has the chance to evaluate them and write the result into the output. For matrices and vectors with container semantics, this makes it easy to create dangling references. Users might not realize that they need to assign expressions to named types before actual work and storage happen. Eigen’s documentation describes this common problem.

Our scaled, conjugated, transposed, and conjugate_transposed functions make use of one aspect of expression templates, namely modifying the mdspan array access operator. However, we intend these functions for use only as in-place modifications of arguments of a function call. Also, when modifying mdspan, these functions merely view the same data that their input mdspan views. They introduce no more potential for dangling references than mdspan itself. The use of views like mdspan is self-documenting; it tells users that they need to take responsibility for scope of the viewed data.

10.5. Banded matrix layouts

This proposal omits banded matrix types. It would be easy to add the required layouts and specializations of algorithms later. The packed and unpacked symmetric and triangular layouts in this proposal cover the major concerns that would arise in the banded case, like nonstrided and nonunique layouts, and matrix types that forbid access to some multi-indices in the Cartesian product of extents.

10.6. Tensors

We exclude tensors from this proposal, for the following reasons. First, tensor libraries naturally build on optimized dense linear algebra libraries like the BLAS, so a linear algebra library is a good first step. Second, mdspan has natural use as a low-level representation of dense tensors, so we are already partway there. Third, even simple tensor operations that naturally generalize the BLAS have infintely many more cases than linear algebra. It’s not clear to us which to optimize. Fourth, even though linear algebra is a special case of tensor algebra, users of linear algebra have different interface expectations than users of tensor algebra. Thus, it makes sense to have two separate interfaces.

10.7. Explicit support for asynchronous return of scalar values

After we presented revision 2 of this paper, LEWG asked us to consider support for discrete graphics processing units (GPUs). GPUs have two features of interest here. First, they might have memory that is not accessible from ordinary C++ code, but could be accessed in a standard algorithm (or one of our proposed algorithms) with the right implementation-specific ExecutionPolicy. (For instance, a policy could say "run this algorithm on the GPU.") Second, they might execute those algorithms asynchronously. That is, they might write to output arguments at some later time after the algorithm invocation returns. This would imply different interfaces in some cases. For instance, a hypothetical asynchronous vector 2-norm might write its scalar result via a pointer to GPU memory, instead of returning the result "on the CPU."

Nothing in principle prevents mdspan from viewing memory that is inaccessible from ordinary C++ code. This is a major feature of the Kokkos::View class from the Kokkos library, and Kokkos::View directly inspired mdspan. The C++ Standard does not currently define how such memory behaves, but implementations could define its behavior and make it work with mdspan. This would, in turn, let implementations define our algorithms to operate on such memory efficiently, if given the right implementation-specific ExecutionPolicy.

Our proposal excludes algorithms that might write to their output arguments at some time after after the algorithm returns. First, LEWG insisted that our proposed algorithms that compute a scalar result, like vector_norm2, return that result in the manner of reduce, rather than writing the result to an output reference or pointer. (Previous revisions of our proposal used the latter interface pattern.) Second, it’s not clear whether writing a scalar result to a pointer is the right interface for asynchronous algorithms. Follow-on proposals to Executors (P0443R14) include asynchronous algorithms, but none of these suggest returning results asynchronously by pointer. Our proposal deliberately imitates the existing standard algorithms. Right now, we have no standard asynchronous algorithms to imitate.

11. Design justification

We take a step-wise approach. We begin with core BLAS dense linear algebra functionality. We then deviate from that only as much as necessary to get algorithms that behave as much as reasonable like the existing C++ Standard Library algorithms. Future work or collaboration with other proposals could implement a higher-level interface.

We propose to build the initial interface on top of mdspan, and plan to extend that later with overloads for a new mdarray variant of mdspan with container semantics as well as any type implementing a get_mdspan customization point. We explain the value of these choices below.

Please refer to our papers "Evolving a Standard C++ Linear Algebra Library from the BLAS" (P1674R1) and "Historical lessons for C++ linear algebra library standardization" (P1417R0). They will give details and references for many of the points that we summarize here.

11.1. We do not require using the BLAS library

Our proposal is based on the BLAS interface, and it would be natural for implementers to use an existing C or Fortran BLAS library. However, we do not require an underlying BLAS C interface. Vendors should have the freedom to decide whether they want to rely on an existing BLAS library. They may also want to write a "pure" C++ implementation that does not depend on an external library. They will, in any case, need a "generic" C++ implementation for matrix and vector element types other than the four that the BLAS supports.

11.2. Why use mdspan?

11.2.1. View of a multidimensional array

The BLAS operates on what C++ programmers might call views of multidimensional arrays. Users of the BLAS can store their data in whatever data structures they like, and handle their allocation and lifetime as they see fit, as long as the data have a BLAS-compatible memory layout.

The corresponding C++ data structure is mdspan. This class encapsulates the large number of pointer and integer arguments that BLAS functions take, that represent views of matrices and vectors. Using mdspan in the C++ interface reduce the number of arguments and avoids common errors, like mixing up the order of arguments. It supports all the array memory layouts that the BLAS supports, including row major and column major. It also expresses the same data ownership model that the BLAS expresses. Users may manage allocation and deallocation however they wish. In addition, mdspan lets our algorithms exploit any dimensions known at compile time.

11.2.2. Ease of use

The mdspan class' layout and accessor policies let us simplify our interfaces, by encapsulating transpose, conjugate, and scalar arguments. Features of mdspan make implementing BLAS-like algorithms much less error prone and easier to read. These include its encapsulation of matrix indexing and its built-in "slicing" capabilities via submdspan.

11.2.3. BLAS and mdspan are low level

The BLAS is low level; it imposes no mathematical meaning on multidimensional arrays. This gives users the freedom to develop mathematical libraries with the semantics they want. Similarly, mdspan is just a view of a multidimensional array; it has no mathematical meaning on its own.

We mention this because "matrix," "vector," and "tensor" are mathematical ideas that mean more than just arrays of numbers. This is more than just a theoretical concern. Some BLAS functions operate on "triangular," "symmetric," or "Hermitian" matrices, but they do not assert that a matrix has any of these mathematical properties. Rather, they only read only one side of the matrix (the lower or upper triangle), and compute as if the rest of the matrix satisfies the mathematical property. A key feature of the BLAS and libraries that build on it, like LAPACK, is that they can operate on the matrix’s data in place. These operations change both the matrix’s mathematical properties and its representation in memory. For example, one might have an N x N array representing a matrix that is symmetric in theory, but computed and stored in a way that might not result in exactly symmetric data. In order to solve linear systems with this matrix, one might give the array to LAPACK’s xSYTRF to compute an LDL^T factorization, asking xSYTRF only to access the array’s lower triangle. If xSYTRF finishes successfully, it has overwritten the lower triangle of its input with a representation of both the lower triangular factor L and the block diagonal matrix D, as computed assuming that the matrix is the sum of the lower triangle and the transpose of the lower triangle. The resulting N x N array no longer represents a symmetric matrix. Rather, it contains part of the representation of a LDL^T factorization of the matrix. The upper triangle still contains the original input matrix’s data. One may then solve linear systems by giving xSYTRS the lower triangle, along with other output of xSYTRF.

The point of this example is that a "symmetric matrix class" is the wrong way to model this situation. There’s an N x N array, whose mathematical interpretation changes with each in-place operation performed on it. The low-level mdspan data structure carries no mathematical properties in itself, so it models this situation better.

11.2.4. Hook for future expansion

The mdspan class treats its layout as an extension point. This lets our interface support layouts beyond what the BLAS Standard permits. The accessor extension point offers us a hook for future expansion to support heterogeneous memory spaces. (This is a key feature of Kokkos::View, the data structure that inspired mdspan.) In addition, using mdspan will make it easier for us to add an efficient "batched" interface in future proposals.

11.2.5. Generic enough to replace a "multidimensional array concept"

LEWGI requested in the 2019 Cologne meeting that we explore using a concept instead of mdspan to define the arguments for the linear algebra functions. This would mean, instead of having our functions take mdspan parameters, they would be generic on one or more suitably constrained multidimensional array types. The constraints would form a "multidimensional array concept."

We investigated this option, and rejected it, for the following reasons.

  1. Our proposal uses enough features of mdspan that any concept generally applicable to all functions we propose would largely replicate the definition of mdspan.

  2. This proposal could support most multidimensional array types, if the array types just made themselves convertible to mdspan.

  3. We could always generalize our algorithms later.

  4. Any multidimensional array concept would need revision in the light of P2128R6.

This proposal refers to almost all of mdspan's features, including extents, layout, and accessor_policy. We expect implementations to use all of them for optimizations, for example to extract the scaling factor from the return value of scaled in order to call an optimized BLAS library directly.

Suppose that a general customization point get_mdspan existed, that takes a reference to a multidimensional array type and returns an mdspan that views the array. Then, our proposal could support most multidimensional array types. "Most" includes all such types that refer to a subset of a contiguous span of memory.

Requiring that a multidimensional array refer to a subset of a contiguous span of memory would exclude multidimensional array types that have a noncontiguous backing store, such as a map. If we later wanted to support such types, we could always generalize our algorithms later.

Finally, any multidimensional array concept would need revision in the light of P2128R6, which has been approved at Plenary. P2128 lets operator[] take multiple parameters. Its authors intend to let mdspan use operator[] instead of operator(). P0009 has adopted this change.

After further discussion at the 2019 Belfast meeting, LEWGI accepted our position that having our algorithms take mdspan instead of template parameters constrained by a multidimensional array concept would be fine for now.

11.3. Function argument aliasing and zero scalar multipliers

Summary:

  1. The BLAS Standard forbids aliasing any input (read-only) argument with any output (write-only or read-and-write) argument.

  2. The BLAS uses INTENT(INOUT) (read-and-write) arguments to express "updates" to a vector or matrix. By contrast, C++ Standard algorithms like transform take input and output iterator ranges as different parameters, but may let input and output ranges be the same.

  3. The BLAS uses the values of scalar multiplier arguments ("alpha" or "beta") of vectors or matrices at run time, to decide whether to treat the vectors or matrices as write only. This matters both for performance and semantically, assuming IEEE floating-point arithmetic.

  4. We decide separately, based on the category of BLAS function, how to translate INTENT(INOUT) arguments into a C++ idiom:

a. For triangular solve and triangular multiply, in-place behavior is essential for computing matrix factorizations in place, without requiring extra storage proportional to the input matrix’s dimensions. However, in-place functions may hinder implementations' use of some forms of parallelism. Thus, we have both not-in-place and in-place overloads. Both take an optional ExecutionPolicy&&, as some forms of parallelism (e.g., vectorization) may still be effective with in-place operations.

b. Else, if the BLAS function unconditionally updates (like xGER), we retain read-and-write behavior for that argument.

c. Else, if the BLAS function uses a scalar beta argument to decide whether to read the output argument as well as write to it (like xGEMM), we provide two versions: a write-only version (as if beta is zero), and a read-and-write version (as if beta is nonzero).

For a detailed analysis, please see our paper "Evolving a Standard C++ Linear Algebra Library from the BLAS" (P1674R1).

11.4. Support for different matrix layouts

Summary:

  1. The dense BLAS supports several different dense matrix "types." Type is a mixture of "storage format" (e.g., packed, banded) and "mathematical property" (e.g., symmetric, Hermitian, triangular).

  2. Some "types" can be expressed as custom mdspan layouts. Other types actually represent algorithmic constraints: for instance, what entries of the matrix the algorithm is allowed to access.

  3. Thus, a C++ BLAS wrapper cannot overload on matrix "type" simply by overloading on mdspan specialization. The wrapper must use different function names, tags, or some other way to decide what the matrix type is.

For more details, including a list and description of the matrix "types" that the dense BLAS supports, please see our paper "Evolving a Standard C++ Linear Algebra Library from the BLAS" (P1674R1).

A C++ linear algebra library has a few possibilities for distinguishing the matrix "type":

  1. It could imitate the BLAS, by introducing different function names, if the layouts and accessors do not sufficiently describe the arguments.

  2. It could introduce a hierarchy of higher-level classes for representing linear algebra objects, use mdspan (or something like it) underneath, and write algorithms to those higher-level classes.

  3. It could use the layout and accessor types in mdspan simply as tags to indicate the matrix "type." Algorithms could specialize on those tags.

We have chosen Approach 1. Our view is that a BLAS-like interface should be as low-level as possible. Approach 2 is more like a "Matlab in C++"; a library that implements this could build on our proposal’s lower-level library. Approach 3 sounds attractive. However, most BLAS matrix "types" do not have a natural representation as layouts. Trying to hack them in would pollute mdspan -- a simple class meant to be easy for the compiler to optimize -- with extra baggage for representing what amounts to sparse matrices. We think that BLAS matrix "type" is better represented with a higher-level library that builds on our proposal.

11.5. Over- and underflow wording for vector 2-norm

SG6 recommended to us at Belfast 2019 to change the special overflow / underflow wording for vector_norm2 to imitate the BLAS Standard more closely. The BLAS Standard does say something about overflow and underflow for vector 2-norms. We reviewed this wording and conclude that it is either a nonbinding quality of implementation (QoI) recommendation, or too vaguely stated to translate directly into C++ Standard wording. Thus, we removed our special overflow / underflow wording. However, the BLAS Standard clearly expresses the intent that implementations document their underflow and overflow guarantees for certain functions, like vector 2-norms. The C++ Standard requires documentation of "implementation-defined behavior." Therefore, we added language to our proposal that makes "any guarantees regarding overflow and underflow" of those certain functions "implementation-defined."

Previous versions of this paper asked implementations to compute vector 2-norms "without undue overflow or underflow at intermediate stages of the computation." "Undue" imitates existing C++ Standard wording for hypot. This wording hints at the stricter requirements in F.9 (normative, but optional) of the C Standard for math library functions like hypot, without mandating those requirements. In particular, paragraph 9 of F.9 says:

Whether or when library functions raise an undeserved "underflow" floating-point exception is unspecified. Otherwise, as implied by F.7.6, the <math.h> functions do not raise spurious floating-point exceptions (detectable by the user) [including the "overflow" exception discussed in paragraph 6], other than the "inexact" floating-point exception.

However, these requirements are for math library functions like hypot, not for general algorithms that return floating-point values. SG6 did not raise a concern that we should treat vector_norm2 like a math library function; their concern was that we imitate the BLAS Standard’s wording.

The BLAS Standard says of several operations, including vector 2-norm: "Here are the exceptional routines where we ask for particularly careful implementations to avoid unnecessary over/underflows, that could make the output unnecessarily inaccurate or unreliable" (p. 35).

The BLAS Standard does not define phrases like "unnecessary over/underflows." The likely intent is to avoid naïve implementations that simply add up the squares of the vector elements. These would overflow even if the norm in exact arithmetic is significantly less than the overflow threshold. The POSIX Standard (IEEE Std 1003.1-2017) analogously says that hypot must "take precautions against overflow during intermediate steps of the computation."

The phrase "precautions against overflow" is too vague for us to translate into a requirement. The authors likely meant to exclude naïve implementations, but not require implementations to know whether a result computed in exact arithmetic would overflow or underflow. The latter is a special case of computing floating-point sums exactly, which is costly for vectors of arbitrary length. While it would be a useful feature, it is difficult enough that we do not want to require it, especially since the BLAS Standard itself does not. The implementation of vector 2-norms in the Reference BLAS included with LAPACK 3.10.0 partitions the running sum of squares into three different accumulators: one for big values (that might cause the sum to overflow without rescaling), one for small values (that might cause the sum to underflow without rescaling), and one for the remaining "medium" values. (See Anderson 2017.) Earlier implementations merely rescaled by the current maximum absolute value of all the vector entries seen thus far. (See Blue 1978.) Implementations could also just compute the sum of squares in a straightforward loop, then check floating-point status flags for underflow or overflow, and recompute if needed.

For all of the functions listed on p. 35 of the BLAS Standard as needing "particularly careful implementations," except vector norm, the BLAS Standard has an "Advice to implementors" section with extra accuracy requirements. The BLAS Standard does have an "Advice to implementors" section for matrix norms (see Section 2.8.7, p. 69), which have similar over- and underflow concerns as vector norms. However, the Standard merely states that "[h]igh-quality implementations of these routines should be accurate" and should document their accuracy, and gives examples of "accurate implementations" in LAPACK.

The BLAS Standard never defines what "Advice to implementors" means. However, the BLAS Standard shares coauthors and audience with the Message Passing Interface (MPI) Standard, which defines "Advice to implementors" as "primarily commentary to implementors" and permissible to skip (see e.g., MPI 3.0, Section 2.1, p. 9). We thus interpret "Advice to implementors" in the BLAS Standard as a nonbinding quality of implementation (QoI) recommendation.

11.6. Constraining matrix and vector element types and scalars

11.6.1. Introduction

The BLAS only accepts four different types of scalars and matrix and vector elements. In C++ terms, these correspond to float, double, complex<float>, and complex<double>. The algorithms we propose generalize the BLAS by accepting any matrix, vector, or scalar element types that make sense for each algorithm. Those may be built-in types, like floating-point numbers or integers, or they may be custom types. Those custom types might not behave like conventional real or complex numbers. For example, quaternions have noncommutative multiplication (a * b might not equal b * a), polynomials in one variable over a field lack division, and some types might not even have subtraction defined. Nevertheless, many BLAS operations would make sense for all of these types.

"Constraining matrix and vector element types and scalars" means defining how these types must behave in order for our algorithms to make sense. This includes both syntactic and semantic constraints. We have three goals:

  1. to help implementers implement our algorithms correctly;

  2. to give implementers the freedom to make quality of implementation (QoI) enhancements, for both performance and accuracy; and

  3. to help users understand what types they may use with our algorithms.

The whole point of the BLAS was to identify key operations for vendors to optimize. Thus, performance is a major concern. "Accuracy" here refers to either to rounding error or to approximation error (for matrix or vector element types where either makes sense).

11.6.2. Value type constraints do not suffice to describe algorithm behavior

LEWG’s 2020 review of P1673R2 asked us to investigate conceptification of its algorithms. "Conceptification" here refers to an effort like that of P1813R0 ("A Concept Design for the Numeric Algorithms"), to come up with concepts that could be used to constrain the template parameters of numeric algorithms like reduce or transform. (We are not referring to LEWGI’s request for us to consider generalizing our algorithm’s parameters from mdspan to a hypothetical multidimensional array concept. We discuss that above, in the "Why use mdspan?" section.) The numeric algorithms are relevant to P1673 because many of the algorithms proposed in P1673 look like generalizations of reduce or transform. We intend for our algorithms to be generic on their matrix and vector element types, so these questions matter a lot to us.

We agree that it is useful to set constraints that make it possible to reason about correctness of algorithms. However, we do not think constraints on value types suffice for this purpose. First, requirements like associativity are too strict to be useful for practical types. Second, what we really want to do is describe the behavior of algorithms, regardless of value types' semantics. "The algorithm may reorder sums" means something different than "addition on the terms in the sum is associative."

11.6.3. Associativity is too strict

P1813R0 requires associative addition for many algorithms, such as reduce. However, many practical arithmetic systems that users might like to use with algorithms like reduce have non-associative addition. These include

Note that the latter two arithmetic systems have nothing to do with rounding error. With saturating integer arithmetic, parenthesizing a sum in different ways might give results that differ by as much as the saturation threshold. It’s true that many non-associative arithmetic systems behave "associatively enough" that users don’t fear parallelizing sums. However, a concept with an exact property (like "commutative semigroup") isn’t the right match for "close enough," just like operator== isn’t the right match for describing "nearly the same." For some number systems, a rounding error bound might be more appropriate, or guarantees on when underflow or overflow may occur (as in POSIX’s hypot).

The problem is a mismatch between the requirement we want to express —that "the algorithm may reparenthesize addition" —and the constraint that "addition is associative." The former describes the algorithm’s behavior, while the latter describes the types used with that algorithm. Given the huge variety of possible arithmetic systems, an approach like the Standard’s use of GENERALIZED_SUM to describe reduce and its kin seems more helpful. If the Standard describes an algorithm in terms of GENERALIZED_SUM, then that tells the caller what the algorithm might do. The caller then takes responsibility for interpreting the algorithm’s results.

We think this is important both for adding new algorithms (like those in this proposal) and for defining behavior of an algorithm with respect to different ExecutionPolicy arguments. (For instance, execution::par_unseq could imply that the algorithm might change the order of terms in a sum, while execution::par need not. Compare to MPI_Op_create's commute parameter, that affects the behavior of algorithms like MPI_Reduce when used with the resulting user-defined reduction operator.)

11.6.4. Generalizing associativity helps little

Suppose we accept that associativity and related properties are not useful for describing our proposed algorithms. Could there be a generalization of associativity that would be useful? P1813R0’s most general concept is a magma. Mathematically, a magma is a set M with a binary operation ×, such that if a and b are in M, then a × b is in M. The operation need not be associative or commutative. While this seems almost too general to be useful, there are two reasons why even a magma is too specific for our proposal.

  1. A magma only assumes one set, that is, one type. This does not accurately describe what the algorithms do, and it excludes useful features like mixed precision and types that use expression templates.

  2. A magma is too specific, because algorithms are useful even if the binary operation is not closed.

First, even for simple linear algebra operations that "only" use plus and times, there is no one "set M" over which plus and times operate. There are actually three operations: plus, times, and assignment. Each operation may have completely heterogeneous input(s) and output. The sets (types) that may occur vary from algorithm to algorithm, depending on the input type(s), and the algebraic expression(s) that the algorithm is allowed to use. We might need several different concepts to cover all the expressions that algorithms use, and the concepts would end up being less useful to users than the expressions themselves.

For instance, consider the Level 1 BLAS "AXPY" function. This computes y[i] = alpha * x[i] + y[i] elementwise. What type does the expression alpha * x[i] + y[i] have? It doesn’t need to have the same type as y[i]; it just needs to be assignable to y[i]. The types of alpha, x[i], and y[i] could all differ. As a simple example, alpha might be int, x[i] might be float, and y[i] might be double. The types of x[i] and y[i] might be more complicated; e.g., x[i] might be a polynomial with double coefficients, and y[i] a polynomial with float coefficients. If those polynomials use expression templates, then slightly different sum expressions involving x[i] and/or y[i] (e.g., alpha * x[i] + y[i], x[i] + y[i], or y[i] + x[i]) might all have different types, all of which differ from value type of x or y. All of these types must be assignable and convertible to the output value type.

We could try to describe this with a concept that expresses a sum type. The sum type would include all the types that might show up in the expression. However, we do not think this would improve clarity over just the expression itself. Furthermore, different algorithms may need different expressions, so we would need multiple concepts, one for each expression. Why not just use the expressions to describe what the algorithms can do?

Second, the magma concept is not helpful even if we only had one set M, because our algorithms would still be useful even if binary operations were not closed over that set. For example, consider a hypothetical user-defined rational number type, where plus and times throw if representing the result of the operation would take more than a given fixed amount of memory. Programmers might handle this exception by falling back to different algorithms. Neither plus or times on this type would satisfy the magma requirement, but the algorithms would still be useful for such a type. One could consider the magma requirement satisfied in a purely syntactic sense, because of the return type of plus and times. However, saying that would not accurately express the type’s behavior.

This point returns us to the concerns we expressed earlier about assuming associativity. "Approximately associative" or "usually associative" are not useful concepts without further refinement. The way to refine these concepts usefully is to describe the behavior of a type fully, e.g., the way that IEEE 754 describes the behavior of floating-point numbers. However, algorithms rarely depend on all the properties in a specification like IEEE 754. The problem, again, is that we need to describe what algorithms do -- e.g., that they can rearrange terms in a sum -- not how the types that go into the algorithms behave.

In summary:

In the sections that follow, we will describe a different way to constrain the matrix and vector element types and scalars in our algorithms. We will start by categorizing the different quality of implementation (QoI) enhancements that implementers might like to make. These enhancements call for changing algorithms in different ways. We will distinguish textbook from non-textbook ways of changing algorithms, explain that we only permit non-textbook changes for floating-point types, then develop constraints on types that permit textbook changes.

11.6.5. Categories of QoI enhancements

An important goal of constraining our algorithms is to give implementers the freedom to make QoI enhancements. We categorize QoI enhancements in three ways:

  1. those that depend entirely on the computer architecture;

  2. those that might have architecture-dependent parameters, but could otherwise be written in an architecture-independent way; and

  3. those that diverge from a textbook description of the algorithm, and depend on element types having properties more specific than what that description requires.

An example of Category (1) would be special hardware instructions that perform matrix-matrix multiplications on small, fixed-size blocks. The hardware might only support a few types, such as integers, fixed-point reals, or floating-point types. Implementations might use these instructions for the entire algorithm, if the problem sizes and element types match the instruction’s requirements. They might also use these instructions to solve subproblems. In either case, these instructions might reorder sums or create temporary values.

Examples of Category (2) include blocking to increase cache or translation lookaside buffer (TLE) reuse, or using SIMD instructions (given the Parallelism TS' inclusion of SIMD). Many of these optimizations relate to memory locality or parallelism. For an overview, see (Goto 2008) or Section 2.6 of (Demmel 1997). All such optimizations reorder sums and create temporary values.

Examples of Category (3) include Strassen’s algorithm for matrix multiplication. The textbook formulation of matrix multiplication only uses additions and multiplies, but Strassen’s algorithm also performs subtractions. A common feature of Category (3) enhancements is that their implementation diverges from a "textbook description of the algorithm" in ways beyond just reordering sums. As a "textbook," we recommend either (Strang 2016), or the concise mathematical description of operations in the BLAS Standard. In the next section, we will list properties of textbook descriptions, and explain some ways in which QoI enhancements might fail to adhere to those properties.

11.6.6. Properties of textbook algorithm descriptions

"Textbook descriptions" of the algorithms we propose tend to have the following properties. For each property, we give an example of a "non-textbook" algorithm, and how it assumes something extra about the matrix’s element type.

a. They compute floating-point sums straightforwardly (possibly reordered, or with temporary intermediate values), rather than using any of several algorithms that improve accuracy (e.g., compensated summation) or even make the result independent of evaluation order (see Demmel 2013). All such non-straightforward algorithms depend on properties of floating-point arithmetic. We will define below what "possibly reordered, or with temporary intermediate values" means.

b. They use only those arithmetic operations on the matrix and vector element types that the textbook description of the algorithm requires, even if using other kinds of arithmetic operations would improve performance or give an asymptotically faster algorithm.

c. They use exact algorithms (not considering rounding error), rather than approximations (that would not be exact even if computing with real numbers).

d. They do not use parallel algorithms that would give an asymptotically faster parallelization in the theoretical limit of infinitely many available parallel processing units, at the cost of likely unacceptable rounding error in floating-point arithmetic.

As an example of (b), the textbook matrix multiplication algorithm only adds or multiplies the matrices' elements. In contrast, Strassen’s algorithm for matrix-matrix multiply subtracts as well as adds and multiplies the matrices' elements. Use of subtraction assumes that arbitrary elements have an additive inverse, but the textbook matrix multiplication algorithm makes sense even for element types that lack additive inverses for all elements. Also, use of subtractions changes floating-point rounding behavior in a way that was only fully understood recently (see Demmel 2007).

As an example of (c), the textbook substitution algorithm for solving triangular linear systems is exact. In contrast, one can approximate triangular solve with a stationary iteration. (See, e.g., Section 5 of (Chow 2015). That paper concerns the sparse matrix case; we cite it merely as an example of an approximate algorithm, not as a recommendation for dense triangular solve.) Approximation only makes sense for element types that have enough precision for the approximation to be accurate. If the approximation checks convergence, than the algorithm also requires less-than comparison of absolute values of differences.

Multiplication by the reciprocal of a number, rather than division by that number, could fit into (b) or (c). As an example of (c), implementations for hardware where floating-point division is slow compared with multiplication could use an approximate reciprocal multiplication to implement division.

As an example of (d), the textbook substitution algorithm for solving triangular linear systems has data dependencies that limit its theoretical parallelism. In contrast, one can solve a triangular linear system by building all powers of the matrix in parallel, then solving the linear system as with a Krylov subspace method. This approach is exact for real numbers, but commits too much rounding error to be useful in practice for all but the smallest linear systems. In fact, the algorithm requires that the matrix’s element type have precision exponential in the matrix’s dimension.

Many of these non-textbook algorithms rely on properties of floating-point arithmetic. Strassen’s algorithm makes sense for unsigned integer types, but it could lead to unwarranted and unexpected overflow for signed integer types. Thus, we think it best to limit implementers to textbook algorithms, unless all matrix and vector element types are floating-point types. We always forbid non-textbook algorithms of type (d). If all matrix and vector element types are floating-point types, we permit non-textbook algorithms of Types (a), (b), and (c), under two conditions:

  1. they satisfy the complexity requirements; and

  2. they result in a logarithmically stable algorithm, in the sense of (Demmel 2007).

We believe that Condition (2) is a reasonable interpretation of Section 2.7 of the BLAS Standard. This says that "no particular computational order is mandated by the function specifications. In other words, any algorithm that produces results 'close enough' to the usual algorithms presented in a standard book on matrix computations is acceptable." Examples of what the BLAS Standard considers "acceptable" include Strassen’s algorithm, and implementing matrix multiplication as C = (alpha * A) * B + (beta * C), C = alpha * (A * B) + (beta * C), or C = A * (alpha * B) + (beta * C).

"Textbook algorithms" includes optimizations commonly found in BLAS implementations. This includes any available hardware acceleration, as well as the locality and parallelism optimizations we describe below. Thus, we think restricting generic implementations to textbook algorithms will not overly limit implementers.

The set of floating-point types currently has three members: float, double, and long double. If a proposal like P1467R4 ("Extended floating-point types and standard names") is accepted, it will grow to include implementation-specific types, such as short or extended-precision floats. This "future-proofs" our proposal in some sense, though implementers will need to take care to avoid approximations if the element type lacks the needed precision.

11.6.7. Reordering sums and creating temporaries

Even textbook descriptions of linear algebra algorithms presume the freedom to reorder sums and create temporary values. Optimizations for memory locality and parallelism depend on this. This freedom imposes requirements on algorithms' matrix and vector element types.

We could get this freedom either by limiting our proposal to the Standard’s current arithmetic types, or by forbidding reordering and temporaries for types other than arithmetic types. However, doing so would unnecessarily prevent straightforward optimizations for small and fast types that act just like arithmetic types. This includes so-called "short floats" such as bfloat16 or binary16, extended-precision floating-point numbers, and fixed-point reals. Some of these types may be implementation defined, and others may be user-specified. We intend to permit implementers to optimize for these types as well. This motivates us to describe our algorithms' type requirements in a generic way.

11.6.7.1. Special case: Only one element type

We find it easier to think about type requirements by starting with the assumption that all element and scalar types in algorithms are the same. One can then generalize to input element type(s) that might differ from the output element type and/or scalar result type.

Optimizations for memory locality and parallelism both create temporary values, and change the order of sums. For example, reorganizing matrix data to reduce stride involves making a temporary copy of a subset of the matrix, and accumulating partial sums into the temporary copy. Thus, both kinds of optimizations impose a common set of requirements and assumptions on types. Let value_type be the output mdspan's value_type. Implementations may:

  1. create arbitrarily many objects of type value_type, value-initializing them or direct-initializing them with any existing object of that type;

  2. perform sums in any order; or

  3. replace any value with the sum of that value and a value-initialized value_type object.

Assumption (1) implies that the output value type is semiregular. Contrast with [algorithms.parallel.exec]: "Unless otherwise stated, implementations may make arbitrary copies of elements of type T, from sequences where is_­trivially_­copy_­constructible_­v<T> and is_­trivially_­destructible_­v<T> are true." We omit the trivially constructible and destructible requirements here and permit any semiregular type. Linear algebra algorithms assume mathematical properties that let us impose more specific requirements than general parallel algorithms. Nevertheless, implementations may want to enable optimizations that create significant temporary storage only if the value type is trivially constructible, trivially destructible, and not too large.

Regarding Assumption (2): The freedom to compute sums in any order is not necessarily a type constraint. Rather, it’s a right that the algorithm claims, regardless of whether the type’s addition is associative or commutative. For example, floating-point sums are not associative, yet both parallelization and customary linear algebra optimizations rely on reordering sums. See the above "Value type constraints do not suffice to describe algorithm behavior" section for a more detailed explanation.

Regarding Assumption (3), we do not actually say that value-initialization produces a two-sided additive identity. What matters is what the algorithm’s implementation may do, not whether the type actually behaves in this way.

11.6.7.2. General case: Multiple input element types

An important feature of P1673 is the ability to compute with mixed matrix or vector element types. For instance, add(y, scaled(alpha, x), z) implements the operation z = y + alpha*x, an elementwise scaled vector sum. The element types of the vectors x, y, and z could be all different, and could differ from the type of alpha.

11.6.7.2.1. Accumulate into output value type

Generic algorithms would use the output mdspan's value_type to accumulate partial sums, and for any temporary results. This is the analog of std::reduce's scalar result type T. Implementations for floating-point types might accumulate into higher-precision temporaries, or use other ways to increase accuracy when accumulating partial sums, but the output mdspan's value_type would still control accumulation behavior in general.

11.6.7.2.2. Proxy references or expression templates

  1. Proxy references: The input and/or output mdspan might have an accessor with a reference type other than element_type&. For example, the output mdspan might have a value type value_type, but its reference type might be atomic_ref<value_type>.

  2. Expression templates: The element types themselves might have arithmetic operations that defer the actual computation until the expression is assigned. These "expression template" types typically hold some kind of reference or pointer to their input arguments.

Neither proxy references nor expression template types are semiregular, because they behave like references, not like values. However, we can still require that their underlying value type be semiregular. For instance, the possiblity of proxy references just means that we need to use the output mdspan's value_type when constructing or value-initializing temporary values, rather than trying to deduce the value type from the type of an expression that indexes into the output mdspan. Expression templates just mean that we need to use the output mdspan's value_type to construct or value-initialize temporaries, rather than trying to deduce the temporaries' type from the right-hand side of the expression.

The z = y + alpha*x example above shows that some of the algorithms we propose have multiple terms in a sum on the right-hand side of the expression that defines the algorithm. If algorithms have permission to rearrange the order of sums, then they need to be able to break up such expressions into separate terms, even if some of those expressions are expression templates.

11.6.8. "Textbook" algorithm description in semiring terms

As we explain in the "Value type constraints do not suffice to describe algorithm behavior" section above, we deliberately constrain matrix and vector element types to require associative addition. This means that we do not, for instance, define concepts like "ring" or "group." We cannot even speak of a single set of values that would permit defining things like a "ring" or "group." This is because our algorithms must handle mixed value types, expression templates, and proxy references. However, it may still be helpful to use mathematical language to explain what we mean by "a textbook description of the algorithm."

Most of the algorithms we propose only depend on addition and multiplication. We describe these algorithms in terms of one or more mathematical expressions on elements of a semiring with possibly noncommutative multiplication. The only difference between a semiring and a ring is that a semiring does not require all elements to have an additive inverse. That is, addition is allowed, but not subtraction. Implementers may apply any mathematical transformation to the expressions that would give the same result for any semiring.

11.6.8.1. Why a semiring?

We use a semiring because

  1. we generally want to reorder terms in sums, but we do not want to order terms in products; and

  2. we do not want to assume that subtraction works.

The first is because linear algebra computations are useful for matrix or vector element types with noncommutative multiplication, such as quaternions or matrices. The second is because algebra operations might be useful for signed integers, where a formulation using subtraction risks unexpected undefined behavior.

11.6.8.2. Semirings and testing

It’s important that implementers be able to test our proposed algorithms for custom element types, not just the built-in arithmetic types. We don’t want to require hypothetical "exact real arithmetic" types that take particular expertise to implement. Instead, we propose testing with simple classes built out of unsigned integers. This section is not part of our Standard Library proposal, but we include it to give guidance to implementers and to show that it’s feasible to test our proposal.

11.6.8.3. Commutative multiplication

C++ unsigned integers implement commutative rings. (Rings always have commutative addition; a "commutative ring" has commutative multiplication as well.) We may transform (say) uint32_t into a commutative semiring by wrapping it in a class that does not provide unary or binary operator-. Adding a "tag" template parameter to this class would let implementers build tests for mixed element types.

11.6.8.4. Noncommutative multiplication

The semiring of 2x2 matrices with element type a commutative semiring is itself a semiring, but with noncommutative multiplication. This is a good way to build a noncommutative semiring for testing.

11.6.9. Summary

12. Future work

Summary:

  1. Consider generalizing function parameters to take any type that implements the get_mdspan customization point, including mdarray.

  2. Add batched linear algebra overloads.

12.1. Generalize function parameters

Our functions differ from the C++ Standard algorithms, in that they take a concrete type mdspan with template parameters, rather than any type that satisfies a concept. We think that the template parameters of mdspan fully describe the multidimensional equivalent of a multipass iterator, and that "conceptification" of multidimensional arrays would unnecessarily delay both this proposal and P0009.

In a future proposal, we may consider generalizing our function’s template parameters, to permit any type besides mdspan that implements the get_mdspan customization point, as long as the return value of get_mdspan satisfies the current requirements. get_mdspan would return an mdspan that views its argument’s data.

The mdarray class, proposed in P1684, is the container analog of mdspan. It is a new kind of container, with the same copy behavior as containers like vector. It will be possible to get an mdspan that views an mdarray. Previous versions of this proposal included function overloads that took mdarray directly. The goals were user convenience, and to avoid any potential overhead of conversion to mdspan, especially for very small matrices and vectors. In a future revision of P1684, mdarray will implement a customization point view (final name yet to be decided), that returns an mdspan viewing the elements of the mdarray. This would let users use mdarray directly in our functions. This customization point approach would also simplify using our functions with other matrix and vector types, such as those proposed by P1385. Implementations may optionally add direct overloads of our functions for mdarray or other types. This would address any concerns about overhead of converting from mdarray to mdspan.

12.2. Batched linear algebra

We plan to write a separate proposal that will add "batched" versions of linear algebra functions to this proposal. "Batched" linear algebra functions solve many independent problems all at once, in a single function call. For discussion, see Section 6.2 of our background paper P1417R0. Batched interfaces have the following advantages:

The mdspan data structure makes it easy to represent a batch of linear algebra objects, and to optimize their data layout.

With few exceptions, the extension of this proposal to support batched operations will not require new functions or interface changes. Only the requirements on functions will change. Output arguments can have an additional rank; if so, then the leftmost extent will refer to the batch dimension. Input arguments may also have an additional rank to match; if they do not, the function will use ("broadcast") the same input argument for all the output arguments in the batch.

13. Data structures and utilities borrowed from other proposals

13.1. mdspan

This proposal depends on P0009, which proposes adding multidimensional arrays to the C++ Standard Library. P0009’s main class is mdspan, which is a "view" (in the sense of span) of a multidimensional array. The rank (number of dimensions) is fixed at compile time. Users may specify some dimensions at run time and others at compile time; the type of the mdspan expresses this. mdspan also has two customization points:

13.2. New mdspan layouts in this proposal

Our proposal uses the layout mapping policy of mdspan in order to represent different matrix and vector data layouts. Layout mapping policies as described by P0009 have three basic properties:

P0009 includes three different layouts -- layout_left, layout_right, and layout_stride -- all of which are unique and strided. Only layout_left and layout_right are contiguous.

This proposal includes the following additional layouts:

These layouts have "tag" template parameters that control their properties; see below.

We do not include layouts for unpacked "types," such as Symmetric (SY), Hermitian (HE), and Triangular (TR). Our paper P1674 explains our reasoning. In summary: Their actual layout -- the arrangement of matrix elements in memory -- is the same as General. The only differences are constraints on what entries of the matrix algorithms may access, and assumptions about the matrix’s mathematical properties. Trying to express those constraints or assumptions as "layouts" or "accessors" violates the spirit (and sometimes the law) of mdspan. We address these different matrix types with different function names.

The packed matrix "types" do describe actual arrangements of matrix elements in memory that are not the same as in General. This is why we provide layout_blas_packed. Note that layout_blas_packed is the first addition to the layouts in P0009 that is neither always unique, nor always strided.

Algorithms cannot be written generically if they permit output arguments with nonunique layouts. Nonunique output arguments require specialization of the algorithm to the layout, since there’s no way to know generically at compile time what indices map to the same matrix element. Thus, we will impose the following rule: Any mdspan output argument to our functions must always have unique layout (is_always_unique() is true), unless otherwise specified.

Some of our functions explicitly require outputs with specific nonunique layouts. This includes low-rank updates to symmetric or Hermitian matrices.

14. Acknowledgments

Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International, Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Special thanks to Bob Steagall and Guy Davidson for boldly leading the charge to add linear algebra to the C++ Standard Library, and for many fruitful discussions. Thanks also to Andrew Lumsdaine for his pioneering efforts and history lessons. In addition, I very much appreciate feedback from Davis Herring on constraints wording.

15. References

15.1. References by coathors

15.2. Other references

16. Wording

Text in blockquotes is not proposed wording, but rather instructions for generating proposed wording. The � character is used to denote a placeholder section number which the editor shall determine. First, apply all wording from P0009R16. (This proposal is a "rebase" atop the changes proposed by P0009R16.) At the end of Table � ("Numerics library summary") in [numerics.general], add the following: [linalg], Linear algebra, <linalg>. At the end of [numerics], add all the material that follows.

16.1. Header <linalg> synopsis [linalg.syn]

namespace std::linalg {
// [linalg.tags.order], storage order tags
struct column_major_t;
inline constexpr column_major_t column_major;
struct row_major_t;
inline constexpr row_major_t row_major;

// [linalg.tags.triangle], triangle tags
struct upper_triangle_t;
inline constexpr upper_triangle_t upper_triangle;
struct lower_triangle_t;
inline constexpr lower_triangle_t lower_triangle;

// [linalg.tags.diagonal], diagonal tags
struct implicit_unit_diagonal_t;
inline constexpr implicit_unit_diagonal_t implicit_unit_diagonal;
struct explicit_diagonal_t;
inline constexpr explicit_diagonal_t explicit_diagonal;

// [linalg.layouts.general], class template layout_blas_general
template<class StorageOrder>
class layout_blas_general;

// [linalg.layouts.packed], class template layout_blas_packed
template<class Triangle,
         class StorageOrder>
class layout_blas_packed;

// [linalg.scaled.accessor_scaled], class template accessor_scaled
template<class ScalingFactor,
         class Accessor>
class accessor_scaled;

// [linalg.scaled.scaled], scaled in-place transformation
template<class ScalingFactor,
         class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
scaled(
  const ScalingFactor& s,
  const mdspan<ElementType, Extents, Layout, Accessor>& a);

// [linalg.conj.accessor_conjugate], class template accessor_conjugate
template<class Accessor>
class accessor_conjugate;

// [linalg.conj.conjugated], conjugated in-place transformation
template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
conjugated(
  mdspan<ElementType, Extents, Layout, Accessor> a);

// [linalg.transp.layout_transpose], class template layout_transpose
template<class Layout>
class layout_transpose;

// [linalg.transp.transposed], transposed in-place transformation
template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
transposed(
  mdspan<ElementType, Extents, Layout, Accessor> a);

// [linalg.conj_transp],
// conjugated transposed in-place transformation
template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
conjugate_transposed(
  mdspan<ElementType, Extents, Layout, Accessor> a);

// [linalg.algs.blas1.givens.lartg], compute Givens rotation
template<class Real>
void givens_rotation_setup(const Real a,
                           const Real b,
                           Real& c,
                           Real& s,
                           Real& r);
template<class Real>
void givens_rotation_setup(const complex<Real>& a,
                           const complex<Real>& a,
                           Real& c,
                           complex<Real>& s,
                           complex<Real>& r);

// [linalg.algs.blas1.givens.rot], apply computed Givens rotation
template<class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const Real s);
template<class ExecutionPolicy,
         class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  ExecutionPolicy&& exec,
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const Real s);
template<class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const complex<Real> s);
template<class ExecutionPolicy,
         class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  ExecutionPolicy&& exec,
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const complex<Real> s);
}

// [linalg.algs.blas1.swap], swap elements
template<class inout_object_1_t,
         class inout_object_2_t>
void swap_elements(inout_object_1_t x,
                   inout_object_2_t y);
template<class ExecutionPolicy,
         class inout_object_1_t,
         class inout_object_2_t>
void swap_elements(ExecutionPolicy&& exec,
                   inout_object_1_t x,
                   inout_object_2_t y);

// [linalg.algs.blas1.scal], multiply elements by scalar
template<class Scalar,
         class inout_object_t>
void scale(const Scalar alpha,
           inout_object_t obj);
template<class ExecutionPolicy,
         class Scalar,
         class inout_object_t>
void scale(ExecutionPolicy&& exec,
           const Scalar alpha,
           inout_object_t obj);

// [linalg.algs.blas1.copy], copy elements
template<class in_object_t,
         class out_object_t>
void copy(in_object_t x,
          out_object_t y);
template<class ExecutionPolicy,
         class in_object_t,
         class out_object_t>
void copy(ExecutionPolicy&& exec,
          in_object_t x,
          out_object_t y);

// [linalg.algs.blas1.add], add elementwise
template<class in_object_1_t,
         class in_object_2_t,
         class out_object_t>
void add(in_object_1_t x,
         in_object_2_t y,
         out_object_t z);
template<class ExecutionPolicy,
         class in_object_1_t,
         class in_object_2_t,
         class out_object_t>
void add(ExecutionPolicy&& exec,
         in_object_1_t x,
         in_object_2_t y,
         out_object_t z);

// [linalg.algs.blas1.dot],
// dot product of two vectors

// [linalg.algs.blas1.dot.dotu],
// nonconjugated dot product of two vectors
template<class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dot(in_vector_1_t v1,
      in_vector_2_t v2,
      T init);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dot(ExecutionPolicy&& exec,
      in_vector_1_t v1,
      in_vector_2_t v2,
      T init);
template<class in_vector_1_t,
         class in_vector_2_t>
auto dot(in_vector_1_t v1,
         in_vector_2_t v2) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t>
auto dot(ExecutionPolicy&& exec,
         in_vector_1_t v1,
         in_vector_2_t v2) -> /* see-below */;

// [linalg.algs.blas1.dot.dotc],
// conjugated dot product of two vectors
template<class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dotc(in_vector_1_t v1,
       in_vector_2_t v2,
       T init);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dotc(ExecutionPolicy&& exec,
       in_vector_1_t v1,
       in_vector_2_t v2,
       T init);
template<class in_vector_1_t,
         class in_vector_2_t>
auto dotc(in_vector_1_t v1,
          in_vector_2_t v2) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t>
auto dotc(ExecutionPolicy&& exec,
          in_vector_1_t v1,
          in_vector_2_t v2) -> /* see-below */;

// [linalg.algs.blas1.ssq],
// Scaled sum of squares of a vector’s elements
template<class T>
struct sum_of_squares_result {
  T scaling_factor;
  T scaled_sum_of_squares;
};
template<class in_vector_t,
         class T>
sum_of_squares_result<T> vector_sum_of_squares(
  in_vector_t v,
  sum_of_squares_result<T> init);
sum_of_squares_result<T> vector_sum_of_squares(
  ExecutionPolicy&& exec,
  in_vector_t v,
  sum_of_squares_result<T> init);

// [linalg.algs.blas1.nrm2],
// Euclidean norm of a vector
template<class in_vector_t,
         class T>
T vector_norm2(in_vector_t v,
               T init);
template<class ExecutionPolicy,
         class in_vector_t,
         class T>
T vector_norm2(ExecutionPolicy&& exec,
               in_vector_t v,
               T init);
template<class in_vector_t>
auto vector_norm2(in_vector_t v) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_t>
auto vector_norm2(ExecutionPolicy&& exec,
                  in_vector_t v) -> /* see-below */;

// [linalg.algs.blas1.asum],
// sum of absolute values of vector elements
template<class in_vector_t,
         class T>
T vector_abs_sum(in_vector_t v,
                 T init);
template<class ExecutionPolicy,
         class in_vector_t,
         class T>
T vector_abs_sum(ExecutionPolicy&& exec,
                 in_vector_t v,
                 T init);
template<class in_vector_t>
auto vector_abs_sum(in_vector_t v) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_t>
auto vector_abs_sum(ExecutionPolicy&& exec,
                    in_vector_t v) -> /* see-below */;

// [linalg.algs.blas1.iamax],
// index of maximum absolute value of vector elements
template<class in_vector_t>
extents<>::size_type idx_abs_max(in_vector_t v);
template<class ExecutionPolicy,
         class in_vector_t>
extents<>::size_type idx_abs_max(
  ExecutionPolicy&& exec,
  in_vector_t v);

// [linalg.algs.blas1.matfrobnorm],
// Frobenius norm of a matrix
template<class in_matrix_t,
         class T>
T matrix_frob_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_frob_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
template<class in_matrix_t>
auto matrix_frob_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_frob_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;

// [linalg.algs.blas1.matonenorm],
// One norm of a matrix
template<class in_matrix_t,
         class T>
T matrix_one_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_one_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
template<class in_matrix_t>
auto matrix_one_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_one_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;

// [linalg.algs.blas1.matinfnorm],
// Infinity norm of a matrix
template<class in_matrix_t,
         class T>
T matrix_inf_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_inf_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
template<class in_matrix_t>
auto matrix_inf_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_inf_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;

// [linalg.algs.blas2.gemv],
// general matrix-vector product
template<class in_vector_t,
         class in_matrix_t,
         class out_vector_t>
void matrix_vector_product(in_matrix_t A,
                           in_vector_t x,
                           out_vector_t y);
template<class ExecutionPolicy,
         class in_vector_t,
         class in_matrix_t,
         class out_vector_t>
void matrix_vector_product(ExecutionPolicy&& exec,
                           in_matrix_t A,
                           in_vector_t x,
                           out_vector_t y);
template<class in_vector_1_t,
         class in_matrix_t,
         class in_vector_2_t,
         class out_vector_t>
void matrix_vector_product(in_matrix_t A,
                           in_vector_1_t x,
                           in_vector_2_t y,
                           out_vector_t z);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_matrix_t,
         class in_vector_2_t,
         class out_vector_t>
void matrix_vector_product(ExecutionPolicy&& exec,
                           in_matrix_t A,
                           in_vector_1_t x,
                           in_vector_2_t y,
                           out_vector_t z);

// [linalg.algs.blas2.symv],
// symmetric matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void symmetric_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void symmetric_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);
template<class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void symmetric_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  in_vector_1_t x,
  in_vector_2_t y,
  out_vector_t z);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void symmetric_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  in_vector_1_t x,
  in_vector_2_t y,
  out_vector_t z);

// [linalg.algs.blas2.hemv],
// Hermitian matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void hermitian_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void hermitian_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);
template<class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void hermitian_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_1_t x,
                                     in_vector_2_t y,
                                     out_vector_t z);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void hermitian_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_1_t x,
                                     in_vector_2_t y,
                                     out_vector_t z);

// [linalg.algs.blas2.trmv],
// Triangular matrix-vector product

// [linalg.algs.blas2.trmv.ov],
// Overwriting triangular matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t x,
  out_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t x,
  out_vector_t y);

// [linalg.algs.blas2.trmv.in-place],
// In-place triangular matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t y);

// [linalg.algs.blas2.trmv.up],
// Updating triangular matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void triangular_matrix_vector_product(in_matrix_t A,
                                      Triangle t,
                                      DiagonalStorage d,
                                      in_vector_1_t x,
                                      in_vector_2_t y,
                                      out_vector_t z);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void triangular_matrix_vector_product(ExecutionPolicy&& exec,
                                      in_matrix_t A,
                                      Triangle t,
                                      DiagonalStorage d,
                                      in_vector_1_t x,
                                      in_vector_2_t y,
                                      out_vector_t z);

// [linalg.algs.blas2.trsv],
// Solve a triangular linear system

// [linalg.algs.blas2.trsv.not-in-place],
// Solve a triangular linear system, not in place
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_solve(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t b,
  out_vector_t x);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_solve(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t b,
  out_vector_t x);

// [linalg.algs.blas2.trsv.in-place],
// Solve a triangular linear system, in place
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_solve(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t b);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_solve(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t b);

// [linalg.algs.blas2.rank1.geru],
// nonconjugated rank-1 matrix update
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

// [linalg.algs.blas2.rank1.gerc],
// conjugated rank-1 matrix update
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update_c(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update_c(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

// [linalg.algs.blas2.rank1.syr],
// symmetric rank-1 matrix update
template<class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);

// [linalg.algs.blas2.rank1.her],
// Hermitian rank-1 matrix update
template<class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);

// [linalg.algs.blas2.rank2.syr2],
// symmetric rank-2 matrix update
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

// [linalg.algs.blas2.rank2.her2],
// Hermitian rank-2 matrix update
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

// [linalg.algs.blas3.gemm],
// general matrix-matrix product
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class out_matrix_t>
void matrix_product(in_matrix_1_t A,
                    in_matrix_2_t B,
                    out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class out_matrix_t>
void matrix_product(ExecutionPolicy&& exec,
                    in_matrix_1_t A,
                    in_matrix_2_t B,
                    out_matrix_t C);
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void matrix_product(in_matrix_1_t A,
                    in_matrix_2_t B,
                    in_matrix_3_t E,
                    out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void matrix_product(ExecutionPolicy&& exec,
                    in_matrix_1_t A,
                    in_matrix_2_t B,
                    in_matrix_3_t E,
                    out_matrix_t C);

// [linalg.algs.blas3.symm],
// symmetric matrix-matrix product

// [linalg.algs.blas3.symm.ov.left],
// overwriting symmetric matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

// [linalg.algs.blas3.symm.ov.right],
// overwriting symmetric matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

// [linalg.algs.blas3.symm.up.left],
// updating symmetric matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.algs.blas3.symm.up.right],
// updating symmetric matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.algs.blas3.hemm],
// Hermitian matrix-matrix product

// [linalg.algs.blas3.hemm.ov.left],
// overwriting Hermitian matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

// [linalg.algs.blas3.hemm.ov.right],
// overwriting Hermitian matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

// [linalg.algs.blas3.hemm.up.left],
// updating Hermitian matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.algs.blas3.hemm.up.right],
// updating Hermitian matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.algs.blas3.trmm],
// triangular matrix-matrix product

// [linalg.algs.blas3.trmm.ov.left],
// overwriting triangular matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);

// [linalg.algs.blas3.trmm.ov.right],
// overwriting triangular matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);

// [linalg.algs.blas3.trmm.up.left],
// updating triangular matrix-matrix left product
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.algs.blas3.trmm.up.right],
// updating triangular matrix-matrix right product
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

// [linalg.alg.blas3.rank-k.syrk],
// rank-k symmetric matrix update
template<class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_k_update(
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);
template<class T,
         class ExecutionPolicy,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_k_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);

// [linalg.alg.blas3.rank-k.herk],
// rank-k Hermitian matrix update
template<class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_k_update(
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_k_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);

// [linalg.alg.blas3.rank2k.syr2k],
// rank-2k symmetric matrix update
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2k_update(
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2k_update(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);

// [linalg.alg.blas3.rank2k.her2k],
// rank-2k Hermitian matrix update
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2k_update(
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2k_update(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);

// [linalg.alg.blas3.trsm],
// solve multiple triangular linear systems

// [linalg.alg.blas3.trsm.left],
// solve multiple triangular linear systems
// with triangular matrix on the left
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_left_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_left_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_left_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_left_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);

// [linalg.alg.blas3.trsm.right],
// solve multiple triangular linear systems
// with triangular matrix on the right
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_right_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_right_solve(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_t B,
  out_matrix_t X);
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_right_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_right_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);
}

16.2. Requirements [linalg.reqs]

16.2.1. Value and reference requirements [linalg.reqs.val]

This clause lists the minimum requirements for all algorithms and classes in [linalg], and for the following types:

In this clause, we refer to these types as linear algebra value types. These type requirements are parameterized by the algorithm or method using the type. Each algorithm or method using the type has one or more associated mathematical expressions that defines the algorithm’s or method’s behavior. For each algorithm or method, its mathematical expression(s) are either explicitly stated as such, or are implicitly stated in the algorithm’s or method’s description. The requirements below will refer to those mathematical expression(s).

[Note: This notion of parameterizing requirements on a mathematical expression generalizes GENERALIZED_SUM. --end note]

All of the following requirements presume that the algorithm’s asymptotic complexity requirements, if any, are satisfied.

  1. Any linear algebra value type meets the requirements of semiregular.

  2. The algorithm or method may perform read-only access on any input or output mdspan arbitrarily many times.

  3. The algorithm or method may make arbitrary many objects of any linear algebra value type, value-initializing or direct-initializing them with any existing object of that type.

  4. The algorithm or method may assign arbitrarily many times to any reference resulting from a valid output mdspan access.

  5. If the algorithm’s or method’s mathematical expression uses division and possibly also addition, subtraction, and multiplication, then the algorithm or method evaluates the mathematical expression using a sequence of evaluations of *, *=, /, /=, +, +=, unary -, binary -, -=, and = operators that would produce the correct result when operating on elements of a field with noncommutative multiplication. (We interpret a / b as a times the multiplicative inverse of b.) 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 in the mathematical expression, any numerator, any denominator, and any assignment in the mathematical expression shall be well formed.

  6. Otherwise, if the algorithm’s or method’s mathematical expression uses subtraction and possibly also addition and multiplication, then the algorithm or method evaluates the mathematical expression using a sequence of evaluations of *, *=, +, +=, unary -, binary -, -=, and = operators that would produce the correct result when operating on elements of a ring with noncommutative multiplication. 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 in the mathematical expression, and any assignment in the mathematical expression shall be well formed.

  7. Otherwise, if the algorithm’s or method’s mathematical expression uses multiplication and possibly also addition, then the algorithm or method evaluates the mathematical expression using a sequence of evaluations of *, *=, +, +=, and = operators that would produce the correct result when operating on elements of a semiring with noncommutative multiplication. Any addend, any partial sum of addends in any order, any factor, any partial product of factors respecting their order in the mathematical expression, and any assignment in the mathematical expression shall be well formed.

  8. Otherwise, if the algorithm’s or method’s mathematical expression uses addition, then the algorithm or method evaluates the mathematical expression using a sequence of evaluations of +, +=, and = operators that would produce the correct result when operating on elements of a commutative semigroup. Any addend, any partial sum of addends in any order, and any assignment in the mathematical expression shall be well formed.

  9. If the algorithm’s or method’s mathematical expression includes any of the following:

    a. conj(z) for some expression z,

    b. abs(x) for some expression x, or

    c. sqrt(x) for some expression x,

    but otherwise conforms to case (5), (6), (7), or (8), then the relevant case (5), (6), (7), or (8) applies. In addition, any of the above subexpressions that appear in the algorithm’s or method’s mathematical expression shall be well formed. However, if the mathematical expression includes conj(z) for an expression z that is not convertible to complex<R> for some R, then the conj(z) expression is interpreted as z for this requirement.

  10. If the algorithm or method has an output mdspan, then all addends (or subtrahends, if applicable) in the algorithm’s or method’s mathematical expression are assignable and convertible to the output mdspan's value_type.

  11. The algorithm or method may reorder addends and partial sums in its mathematical expression arbitrarily. [Note: Factors in each product are not reordered; multiplication is not necessarily commutative. --end note]

  12. The algorithm or method may replace any value with the sum of that value and a value-initialized object of any input or output mdspan's value_type.

  13. If the algorithm or method has a T init parameter, then the algorithm or method may replace any value with the sum of that value and a value-initialized object of type T.

16.2.2. Requirements for algorithms and methods on floating-point values [linalg.reqs.flpt]

For all algorithms and classes in [linalg], suppose that

Then, algorithms and classes' methods may do the following:

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

  2. perform arithmetic operations other than those in the algorithm’s or method’s mathematical expression, in order to improve performance or accuracy; and

  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

  1. the algorithm or method satisfies the complexity requirements; and

  2. the algorithm or method is logarithmically stable, in the sense of (Demmel 2007).

[Note: Strassen’s algorithm for matrix-matrix multiply is an example of a logarithmically stable algorithm. --end note]

16.3. Tag classes [linalg.tags]

16.3.1. Storage order tags [linalg.tags.order]

struct column_major_t { };
inline constexpr column_major_t column_major = { };

struct row_major_t { };
inline constexpr row_major_t row_major = { };

column_major_t indicates a column-major order, and row_major_t indicates a row-major order. The interpretation of each depends on the specific layout that uses the tag. See layout_blas_general and layout_blas_packed below.

16.3.2. Triangle tags [linalg.tags.triangle]

Some linear algebra algorithms distinguish between the "upper triangle," "lower triangle," and "diagonal" of a matrix.

struct upper_triangle_t { };
inline constexpr upper_triangle_t upper_triangle = { };

struct lower_triangle_t { };
inline constexpr lower_triangle_t lower_triangle = { };

These tag classes specify whether algorithms and other users of a matrix (represented as an mdspan) should access the upper triangle (upper_triangular_t) or lower triangle (lower_triangular_t) of the matrix. This is also subject to the restrictions of implicit_unit_diagonal_t if that tag is also applied; see below.

16.3.3. Diagonal tags [linalg.tags.diagonal]

struct implicit_unit_diagonal_t { };
inline constexpr implicit_unit_diagonal_t
  implicit_unit_diagonal = { };

struct explicit_diagonal_t { };
inline constexpr explicit_diagonal_t explicit_diagonal = { };

These tag classes specify what algorithms and other users of a matrix should assume about the diagonal entries of the matrix, and whether algorithms and users of the matrix should access those diagonal entries explicitly.

The implicit_unit_diagonal_t tag indicates two things:

The tag explicit_diagonal_t indicates that algorithms and other users of the viewer may access the matrix’s diagonal entries directly.

16.4. Layouts for general and packed matrix types [linalg.layouts]

16.4.1. layout_blas_general [linalg.layouts.general]

layout_blas_general is an mdspan layout mapping policy. Its StorageOrder template parameter determines whether the matrix’s data layout is column major or row major.

layout_blas_general<column_major_t> represents a column-major matrix layout, where the stride between consecutive rows is always one, and the stride between consecutive columns may be greater than or equal to the number of rows. [Note: This is a generalization of layout_left. --end note]

layout_blas_general<row_major_t> represents a row-major matrix layout, where the stride between consecutive rows may be greater than or equal to the number of columns, and the stride between consecutive columns is always one. [Note: This is a generalization of layout_right. --end note]

[Note:

layout_blas_general represents exactly the data layout assumed by the General (GE) matrix type in the BLAS' C binding. It has two advantages:

  1. Unlike layout_left and layout_right, any "submatrix" (subspan of consecutive rows and consecutive columns) of a matrix with layout_blas_general<StorageOrder> layout also has layout_blas_general<StorageOrder> layout.

  2. Unlike layout_stride, it always has compile-time unit stride in one of the matrix’s two extents.

BLAS functions call the possibly nonunit stride of the matrix the "leading dimension" of that matrix. For example, a BLAS function argument corresponding to the leading dimension of the matrix A is called LDA, for "leading dimension of the matrix A."

--end note]

template<class StorageOrder>
class layout_blas_general {
public:
  template<class Extents>
  struct mapping {
  private:
    Extents extents_; // exposition only
    const typename Extents::size_type stride_{}; // exposition only

  public:
    constexpr mapping(const Extents& e,
      const typename Extents::size_type s);

    template<class OtherExtents>
    constexpr mapping(const mapping<OtherExtents>& e) noexcept;

    typename Extents::size_type
    operator() (typename Extents::size_type i,
                typename Extents::size_type j) const;

    constexpr typename Extents::size_type
    required_span_size() const noexcept;

    typename Extents::size_type
    stride(typename Extents::size_type r) const noexcept;

    template<class OtherExtents>
    bool operator==(const mapping<OtherExtents>& m) const noexcept;

    template<class OtherExtents>
    bool operator!=(const mapping<OtherExtents>& m) const noexcept;

    Extents extents() const noexcept;

    static constexpr bool is_always_unique();
    static constexpr bool is_always_contiguous();
    static constexpr bool is_always_strided();

    constexpr bool is_unique() const noexcept;
    constexpr bool is_contiguous() const noexcept;
    constexpr bool is_strided() const noexcept;
  };
};

constexpr mapping(const Extents& e,
  const typename Extents::size_type s);

[Note:

The BLAS Standard requires that the stride be one if the corresponding matrix dimension is zero. We do not impose this requirement here, because it is specific to the BLAS. if an implementation dispatches to a BLAS function, then the implementation must impose the requirement at run time.

--end note]

template<class OtherExtents>
constexpr mapping(const mapping<OtherExtents>& e) noexcept;

typename Extents::size_type
operator() (typename Extents::size_type i,
            typename Extents::size_type j) const;

template<class OtherExtents>
bool operator==(const mapping<OtherExtents>& m) const;

template<class OtherExtents>
bool operator!=(const mapping<OtherExtents>& m) const;

typename Extents::size_type
stride(typename Extents::size_type r) const noexcept;

constexpr typename Extents::size_type
required_span_size() const noexcept;

Extents extents() const noexcept;

static constexpr bool is_always_unique();

static constexpr bool is_always_contiguous();

static constexpr bool is_always_strided();

constexpr bool is_unique() const noexcept;

constexpr bool is_contiguous() const noexcept;

constexpr bool is_strided() const noexcept;

16.4.2. layout_blas_packed [linalg.layouts.packed]

layout_blas_packed is an mdspan layout mapping policy that represents a square matrix that stores only the entries in one triangle, in a packed contiguous format. Its Triangle template parameter determines whether an mdspan with this layout stores the upper or lower triangle of the matrix. Its StorageOrder template parameter determines whether the layout packs the matrix’s elements in column-major or row-major order.

A StorageOrder of column_major_t indicates column-major ordering. This packs matrix elements starting with the leftmost (least column index) column, and proceeding column by column, from the top entry (least row index).

A StorageOrder of row_major_t indicates row-major ordering. This packs matrix elements starting with the topmost (least row index) row, and proceeding row by row, from the leftmost (least column index) entry.

[Note:

layout_blas_packed describes the data layout used by the BLAS' Symmetric Packed (SP), Hermitian Packed (HP), and Triangular Packed (TP) matrix types.

If transposed's input has layout layout_blas_packed, the return type also has layout layout_blas_packed, but with opposite Triangle and StorageOrder. For example, the transpose of a packed column-major upper triangle, is a packed row-major lower triangle.

--end note]

template<class Triangle,
         class StorageOrder>
class layout_blas_packed {
public:
  template<class Extents>
  struct mapping {
  private:
    Extents extents_; // exposition only

  public:
    constexpr mapping(const Extents& e);

    template<class OtherExtents>
    constexpr mapping(const mapping<OtherExtents>& e) noexcept;

    typename Extents::size_type
    operator() (typename Extents::size_type i,
                typename Extents::size_type j) const;

    template<class OtherExtents>
    bool operator==(const mapping<OtherExtents>& m) const noexcept;

    template<class OtherExtents>
    bool operator!=(const mapping<OtherExtents>& m) const noexcept;

    constexpr typename Extents::size_type
    stride(typename Extents::size_type r) const noexcept;

    constexpr typename Extents::size_type
    required_span_size() const noexcept;

    constexpr Extents extents() const noexcept;

    static constexpr bool is_always_unique();
    static constexpr bool is_always_contiguous();
    static constexpr bool is_always_strided();

    constexpr bool is_unique() const noexcept;
    constexpr bool is_contiguous() const noexcept;
    constexpr bool is_strided() const noexcept;
};

constexpr mapping(const Extents& e);

template<class OtherExtents>
constexpr mapping(const mapping<OtherExtents>& e);

typename Extents::size_type
operator() (typename Extents::size_type i,
            typename Extents::size_type j) const;

template<class OtherExtents>
bool operator==(const mapping<OtherExtents>& m) const;

template<class OtherExtents>
bool operator!=(const mapping<OtherExtents>& m) const;

constexpr typename Extents::size_type
stride(typename Extents::size_type r) const noexcept;

constexpr typename Extents::size_type
required_span_size() const noexcept;

constexpr Extents extents() const noexcept;

static constexpr bool is_always_unique();

static constexpr bool is_always_contiguous();

static constexpr bool is_always_strided();

constexpr bool is_unique() const noexcept;

constexpr bool is_contiguous() const noexcept;

constexpr bool is_strided() const noexcept;

16.5. Scaled in-place transformation [linalg.scaled]

The scaled function takes a value alpha and an mdspan x, and returns a new read-only mdspan with the same domain as x, that represents the elementwise product of alpha with each element of x.

[Example:

// z = alpha * x + y
void z_equals_alpha_times_x_plus_y(
  mdspan<double, extents<dynamic_extent>> z,
  const double alpha,
  mdspan<double, extents<dynamic_extent>> x,
  mdspan<double, extents<dynamic_extent>> y)
{
  add(scaled(alpha, x), y, y);
}

// w = alpha * x + beta * y
void w_equals_alpha_times_x_plus_beta_times_y(
  mdspan<double, extents<dynamic_extent>> w,
  const double alpha,
  mdspan<double, extents<dynamic_extent>> x,
  const double beta,
  mdspan<double, extents<dynamic_extent>> y)
{
  add(scaled(alpha, x), scaled(beta, y), w);
}
--end example]

[Note:

An implementation could dispatch to a function in the BLAS library, by noticing that the first argument has an accessor_scaled Accessor type. It could use this information to extract the appropriate run-time value(s) of the relevant BLAS function arguments (e.g., ALPHA and/or BETA), by calling accessor_scaled::scaling_factor.

--end note]

16.5.1. Class template accessor_scaled [linalg.scaled.accessor_scaled]

The class template accessor_scaled is an mdspan accessor policy whose reference type represents the product of a fixed value (the "scaling factor") and its nested mdspan accessor’s reference. It is part of the implementation of scaled.

The exposition-only class template scaled_scalar represents a read-only value, which is the product of a fixed value (the "scaling factor") and the value of a reference to an element of a mdspan. [Note: The value is read only to avoid confusion with the definition of "assigning to a scaled scalar." --end note] scaled_scalar is part of the implementation of scaled_accessor.

template<class ScalingFactor,
         class Reference>
class scaled_scalar { // exposition only
private:
  const ScalingFactor scaling_factor;
  Reference value;
  using result_type =
    decltype (scaling_factor * value);

public:
  scaled_scalar(const ScalingFactor& s, Reference v);

  operator result_type() const;
};

scaled_scalar(const ScalingFactor& s, Reference v);

operator result_type() const;

The class template accessor_scaled is an mdspan accessor policy whose reference type represents the product of a scaling factor and its nested mdspan accessor’s reference.

template<class ScalingFactor,
         class Accessor>
class accessor_scaled {
public:
  using element_type  = Accessor::element_type;
  using pointer       = Accessor::pointer;
  using reference     =
    scaled_scalar<ScalingFactor, Accessor::reference>;
  using offset_policy =
    accessor_scaled<ScalingFactor, Accessor::offset_policy>;

  accessor_scaled(const ScalingFactor& s, Accessor a);

  reference access(pointer p, extents<>::size_type i) const noexcept;

  offset_policy::pointer
  offset(pointer p, extents<>::size_type i) const noexcept;

  element_type* decay(pointer p) const noexcept;

  ScalingFactor scaling_factor() const;

private:
  const ScalingFactor scaling_factor_; // exposition only
  Accessor accessor; // exposition only
};

accessor_scaled(const ScalingFactor& s, Accessor a);

reference access(pointer p, extents<>::size_type i) const noexcept;

offset_policy::pointer
offset(pointer p, extents<>::size_type i) const noexcept;

element_type* decay(pointer p) const noexcept;

ScalingFactor scaling_factor() const;

16.5.2. scaled [linalg.scaled.scaled]

The scaled function takes a value alpha and an mdspan x, and returns a new read-only mdspan with the same domain as x, that represents the elementwise product of alpha with each element of x.

For i... in the domain of x, the mathematical expression for element i... of scaled(alpha, x) is alpha * x[i...]. [Note: Terms in this product will not be reordered. --end note]

template<class ScalingFactor,
         class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see below */
scaled(
  const ScalingFactor& alpha,
  const mdspan<ElementType, Extents, Layout, Accessor>& x);

Let R name the type mdspan<ReturnElementType, Extents, Layout, ReturnAccessor>, where

[Note:

The point of ReturnAccessor is to give implementations freedom to optimize applying accessor_scaled twice in a row. However, implementations are not required to optimize arbitrary combinations of nested accessor_scaled interspersed with other nested accessors.

The point of ReturnElementType is that mdspan does not provide a generic mechanism for deducing the const version of Accessor for use in accessor_scaled. In general, it may not be correct or efficient to use an Accessor meant for a nonconst ElementType, with const ElementType. This is because Accessor::reference may be a type other than ElementType&. Thus, we cannot require that the return type have const ElementType as its element type, since that might not be compatible with the given Accessor. However, in some cases, like default_accessor, it is possible to deduce the const version of Accessor. Regardless, users are not allowed to modify the elements of the returned mdspan.

--end note]

[Example:

void test_scaled(mdspan<double, extents<10>> x)
{
  auto x_scaled = scaled(5.0, x);
  for(int i = 0; i < x.extent(0); ++i) {
    assert(x_scaled[i] == 5.0 * x[i]);
  }
}
--end example]

16.6. Conjugated in-place transformation [linalg.conj]

The conjugated function takes an mdspan x, and returns a new read-only mdspan y with the same domain as x, whose elements are the complex conjugates of the corresponding elements of x. If the element type of x is not complex<R> for some R, then y is a read-only view of the elements of x.

[Note:

An implementation could dispatch to a function in the BLAS library, by noticing that the Accessor type of an mdspan input has type accessor_conjugate, and that its nested Accessor type is compatible with the BLAS library. If so, it could set the corresponding TRANS* BLAS function argument accordingly and call the BLAS function.

--end note]

16.6.1. Class template accessor_conjugate [linalg.conj.accessor_conjugate]

The class template accessor_conjugate is an mdspan accessor policy whose reference type represents the complex conjugate of its nested mdspan accessor’s reference.

The exposition-only class template conjugated_scalar represents a read-only value, which is the complex conjugate of the value of a reference to an element of an mdspan. [Note: The value is read only to avoid confusion with the definition of "assigning to the conjugate of a scalar." --end note] conjugated_scalar is part of the implementation of accessor_conjugate.

template<class Reference,
         class ElementType>
class conjugated_scalar { // exposition only
public:
  conjugated_scalar(Reference v);

  operator ElementType() const;

  template<class T2>
  auto operator* (const T2 upd) const {
    using std::conj;
    return conj(val) * upd;
  }

  template<class T2>
  auto operator+ (const T2 upd) const {
    using std::conj;
    return conj(val) + upd;
  }

  template<class T2>
  bool operator== (const T2 upd) const {
    using std::conj;
    return conj(val) == upd;
  }

  template<class T2>
  bool operator!= (const T2 upd) const {
    using std::conj;
    return conj(val) != upd;
  }

private:
  Reference val;
};

template<class T1, class Reference, class Element>
auto operator* (const T1 x, const conjugated_scalar<Reference, Element> y) {
  return x * Reference(y);
}

conjugated_scalar(Reference v);

operator T() const;

template<class Accessor>
class accessor_conjugate {
private:
  Accessor acc; // exposition only

public:
  using element_type  = typename Accessor::element_type;
  using pointer       = typename Accessor::pointer;
  using reference     = /* see below */;
  using offset_policy = /* see below */;

  accessor_conjugate(Accessor a);

  reference access(pointer p, extents<>::size_type i) const
    noexcept(noexcept(reference(acc.access(p, i))));

  typename offset_policy::pointer
  offset(pointer p, extents<>::size_type i) const
    noexcept(noexcept(acc.offset(p, i)));

  element_type* decay(pointer p) const
    noexcept(noexcept(acc.decay(p)));

  Accessor nested_accessor() const;
};

using reference = /* see below */;

If element_type is complex<R> for some R, then this names conjugated_scalar<typename Accessor::reference, element_type>. Otherwise, it names typename Accessor::reference.

using offset_policy = /* see below */;

If element_type is complex<R> for some R, then this names accessor_conjugate<typename Accessor::offset_policy, element_type>. Otherwise, it names typename Accessor::offset_policy>.

accessor_conjugate(Accessor a);

reference access(pointer p, extents<>::size_type i) const
  noexcept(noexcept(reference(acc.access(p, i))));

typename offset_policy::pointer
offset(pointer p, extents<>::size_type i) const
  noexcept(noexcept(acc.offset(p, i)));

element_type* decay(pointer p) const
  noexcept(noexcept(acc.decay(p)));

Accessor nested_accessor() const;

16.6.2. conjugated [linalg.conj.conjugated]

template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
conjugated(
  mdspan<ElementType, Extents, Layout, Accessor> a);

Let R name the type mdspan<ReturnElementType, Extents, Layout, ReturnAccessor>, where

[Note:

The point of ReturnAccessor is to give implementations freedom to optimize applying accessor_conjugate twice in a row. However, implementations are not required to optimize arbitrary combinations of nested accessor_conjugate interspersed with other nested accessors.

--end note]

[Example:

void test_conjugated_complex(
  mdspan<complex<double>, extents<10>> a)
{
  auto a_conj = conjugated(a);
  for(int i = 0; i < a.extent(0); ++i) {
    assert(a_conj[i] == conj(a[i]);
  }
  auto a_conj_conj = conjugated(a_conj);
  for(int i = 0; i < a.extent(0); ++i) {
    assert(a_conj_conj[i] == a[i]);
  }
}

void test_conjugated_real(
  mdspan<double, extents<10>> a)
{
  auto a_conj = conjugated(a);
  for(int i = 0; i < a.extent(0); ++i) {
    assert(a_conj[i] == a[i]);
  }
  auto a_conj_conj = conjugated(a_conj);
  for(int i = 0; i < a.extent(0); ++i) {
    assert(a_conj_conj[i] == a[i]);
  }
}
--end example]

16.7. Transpose in-place transformation [linalg.transp]

layout_transpose is an mdspan layout mapping policy that swaps the rightmost two indices, extents, and strides (if applicable) of any unique mdspan layout mapping policy.

The transposed function takes a rank-2 mdspan representing a matrix, and returns a new read-only mdspan representing the transpose of the input matrix.

[Note:

An implementation could dispatch to a function in the BLAS library, by noticing that the first argument has a layout_transpose Layout type, and/or an accessor_conjugate (see below) Accessor type. It could use this information to extract the appropriate run-time value(s) of the relevant TRANS* BLAS function arguments.

--end note]

16.7.1. layout_transpose [linalg.transp.layout_transpose]

layout_transpose is an mdspan layout mapping policy that swaps the rightmost two indices, extents, and strides (if applicable) of any unique mdspan layout mapping policy.

template<class InputExtents>
using transpose_extents_t = /* see below */; // exposition only

For InputExtents a specialization of extents, transpose_extents_t<InputExtents> names the extents type OutputExtents such that

template<class InputExtents>
transpose_extents_t<InputExtents>
transpose_extents(const InputExtents in); // exposition only

template<class Layout>
class layout_transpose {
public:
  template<class Extents>
  struct mapping {
  private:
    using nested_mapping_type =
      typename Layout::template mapping<
        transpose_extents_t<Extents>>; // exposition only
    nested_mapping_type nested_mapping_; // exposition only

  public:
    mapping(const nested_mapping_type& map);

    extents<>::size_type operator() (
      extents<>::size_type i, extents<>::size_type j) const
        noexcept(noexcept(nested_mapping_(j, i)));

    nested_mapping_type nested_mapping() const;

    template<class OtherExtents>
    bool operator==(const mapping<OtherExtents>& m) const;

    template<class OtherExtents>
    bool operator!=(const mapping<OtherExtents>& m) const;

    Extents extents() const noexcept;

    typename Extents::size_type required_span_size() const
      noexcept(noexcept(nested_mapping_.required_span_size()));

    bool is_unique() const
      noexcept(noexcept(nested_mapping_.is_unique()));

    bool is_contiguous() const
      noexcept(noexcept(nested_mapping_.is_contiguous()));

    bool is_strided() const
      noexcept(noexcept(nested_mapping_.is_strided()));

    static constexpr bool is_always_unique();

    static constexpr bool is_always_contiguous();

    static constexpr bool is_always_strided();

    typename Extents::size_type
    stride(typename Extents::size_type r) const
      noexcept(noexcept(nested_mapping_.stride(r)));
  };
};

mapping(const nested_mapping_type& map);

extents<>::size_type operator() (
  extents<>::size_type i, extents<>::size_type j) const
    noexcept(noexcept(nested_mapping_(j, i)));

nested_mapping_type nested_mapping() const;

template<class OtherExtents>
bool operator==(const mapping<OtherExtents>& m) const;

template<class OtherExtents>
bool operator!=(const mapping<OtherExtents>& m) const;

Extents extents() const noexcept;

typename Extents::size_type
required_span_size() const
  noexcept(noexcept(nested_mapping_.required_span_size()));

bool is_unique() const
  noexcept(noexcept(nested_mapping_.is_unique()));

bool is_contiguous() const
  noexcept(noexcept(nested_mapping_.is_contiguous()));

bool is_strided() const
  noexcept(noexcept(nested_mapping_.is_strided()));

static constexpr bool is_always_unique();

static constexpr bool is_always_contiguous();

static constexpr bool is_always_strided();

typename Extents::size_type
stride(typename Extents::size_type r) const
  noexcept(noexcept(nested_mapping_.stride(r)));

16.7.2. transposed [linalg.transp.transposed]

The transposed function takes a rank-2 mdspan representing a matrix, and returns a new read-only mdspan representing the transpose of the input matrix. The input matrix’s data are not modified, and the returned mdspan accesses the input matrix’s data in place. If the input mdspan's layout is already layout_transpose<L> for some layout L, then the returned mdspan has layout L. Otherwise, the returned mdspan has layout layout_transpose<L>, where L is the input mdspan's layout.

template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
transposed(
  mdspan<ElementType, Extents, Layout, Accessor> a);

Let ReturnExtents name the type transpose_extents_t<Extents>. Let R name the type mdspan<ReturnElementType, ReturnExtents, ReturnLayout, Accessor>, where

[Note:

Implementations may optimize applying layout_transpose twice in a row. However, implementations need not optimize arbitrary combinations of nested layout_transpose interspersed with other nested layouts.

--end note]

[Example:

void test_transposed(mdspan<double, extents<3, 4>> a)
{
  const auto num_rows = a.extent(0);
  const auto num_cols = a.extent(1);

  auto a_t = transposed(a);
  assert(num_rows == a_t.extent(1));
  assert(num_cols == a_t.extent(0));
  assert(a.stride(0) == a_t.stride(1));
  assert(a.stride(1) == a_t.stride(0));

  for(extents<>::size_type row = 0; row < num_rows; ++row) {
    for(extents<>::size_type col = 0; col < num_rows; ++col) {
      assert(a[row, col] == a_t[col, row]);
    }
  }

  auto a_t_t = transposed(a_t);
  assert(num_rows == a_t_t.extent(0));
  assert(num_cols == a_t_t.extent(1));
  assert(a.stride(0) == a_t_t.stride(0));
  assert(a.stride(1) == a_t_t.stride(1));

  for(extents<>::size_type row = 0; row < num_rows; ++row) {
    for(extents<>::size_type col = 0; col < num_rows; ++col) {
      assert(a[row, col] == a_t_t[row, col]);
    }
  }
}
--end example]

16.8. Conjugate transpose transform [linalg.conj_transp]

The conjugate_transposed function returns a conjugate transpose view of an object. This combines the effects of transposed and conjugated.

template<class ElementType,
         class Extents,
         class Layout,
         class Accessor>
/* see-below */
conjugate_transposed(
  mdspan<ElementType, Extents, Layout, Accessor> a);

[Example:

void test_conjugate_transposed(
  mdspan<complex<double>, extents<3, 4>> a)
{
  const auto num_rows = a.extent(0);
  const auto num_cols = a.extent(1);

  auto a_ct = conjugate_transposed(a);
  assert(num_rows == a_ct.extent(1));
  assert(num_cols == a_ct.extent(0));
  assert(a.stride(0) == a_ct.stride(1));
  assert(a.stride(1) == a_ct.stride(0));

  for(extents<>::size_type row = 0; row < num_rows; ++row) {
    for(extents<>::size_type col = 0; col < num_rows; ++col) {
      assert(a[row, col] == conj(a_ct[col, row]));
    }
  }

  auto a_ct_ct = conjugate_transposed(a_ct);
  assert(num_rows == a_ct_ct.extent(0));
  assert(num_cols == a_ct_ct.extent(1));
  assert(a.stride(0) == a_ct_ct.stride(0));
  assert(a.stride(1) == a_ct_ct.stride(1));

  for(extents<>::size_type row = 0; row < num_rows; ++row) {
    for(extents<>::size_type col = 0; col < num_rows; ++col) {
      assert(a[row, col] == a_ct_ct[row, col]);
      assert(conj(a_ct[col, row]) == a_ct_ct[row, col]);
    }
  }
}
--end example]

16.9. Algorithms [linalg.algs]

16.9.1. Requirements based on template parameter name [linalg.algs.reqs]

Throughout this Clause, where the template parameters are not constrained, the names of template parameters are used to express type requirements. In the requirements below, we use * in a typename to denote a "wildcard," that matches zero characters, _1, _2, _3, or other things as appropriate.

16.9.2. BLAS 1 functions [linalg.algs.blas1]

[Note:

The BLAS developed in three "levels": 1, 2, and 3. BLAS 1 includes vector-vector operations, BLAS 2 matrix-vector operations, and BLAS 3 matrix-matrix operations. The level coincides with the number of nested loops in a naïve sequential implementation of the operation. Increasing level also comes with increasing potential for data reuse. The BLAS traditionally lists computing a Givens rotation among the BLAS 1 operations, even though it only operates on scalars.

--end note]

Complexity: All algorithms in this Clause with mdspan parameters perform a count of mdspan array accesses and arithmetic operations that is linear in the maximum product of extents of any mdspan parameter.

16.9.2.1. Givens rotations [linalg.algs.blas1.givens]
16.9.2.1.1. Compute Givens rotation [linalg.algs.blas1.givens.lartg]
template<class Real>
void givens_rotation_setup(const Real a,
                           const Real b,
                           Real& c,
                           Real& s,
                           Real& r);

template<class Real>
void givens_rotation_setup(const complex<Real>& a,
                           const complex<Real>& a,
                           Real& c,
                           complex<Real>& s,
                           complex<Real>& r);

This function computes the plane (Givens) rotation represented by the two values c and s such that the 2x2 system of equations

[c        s]   [a]   [r]
[          ] * [ ] = [ ]
[-conj(s) c]   [b]   [0]

holds, where conj indicates the mathematical conjugate of s, c is always a real scalar, and c*c + abs(s)*abs(s) equals one. That is, c and s represent a 2 x 2 matrix, that when multiplied by the right by the input vector whose components are a and b, produces a result vector whose first component r is the Euclidean norm of the input vector, and whose second component as zero. [Note: The C++ Standard Library conj function always returns complex<T> for some T, even though overloads exist for non-complex input. The above expression uses conj as mathematical notation, not as code. --end note]

[Note: This function corresponds to the LAPACK function xLARTG. The BLAS variant xROTG takes four arguments -- a, b, c, and s-- and overwrites the input a with r. We have chosen xLARTG's interface because it separates input and output, and to encourage following xLARTG's more careful implementation. --end note]

[Note: givens_rotation_setup has an overload for complex numbers, because the output argument c (cosine) is a signed magnitude. --end note]

16.9.2.1.2. Apply a computed Givens rotation to vectors [linalg.algs.blas1.givens.rot]
template<class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const Real s);

template<class ExecutionPolicy,
         class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  ExecutionPolicy&& exec,
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const Real s);

template<class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const complex<Real> s);

template<class ExecutionPolicy,
         class inout_vector_1_t,
         class inout_vector_2_t,
         class Real>
void givens_rotation_apply(
  ExecutionPolicy&& exec,
  inout_vector_1_t x,
  inout_vector_2_t y,
  const Real c,
  const complex<Real> s);

[Note: These functions correspond to the BLAS function xROT. c and s form a plane (Givens) rotation. Users normally would compute c and s using givens_rotation_setup, but they are not required to do this. --end note]

For the overloads that take the last argument s as Real, for i in the domains of both x and y, the mathematical expressions for the algorithm are x[i] = c*x[i] + s*y[i] and y[i] = c*y[i] - s*x[i].

For the overloads that take the last argument s as const complex<Real>, for i in the domains of both x and y, the mathematical expressions for the algorithm are x[i] = c*x[i] + s*y[i] and y[i] = c*y[i] - conj(s)*x[i].

16.9.2.2. Swap matrix or vector elements [linalg.algs.blas1.swap]
template<class inout_object_1_t,
         class inout_object_2_t>
void swap_elements(inout_object_1_t x,
                   inout_object_2_t y);

template<class ExecutionPolicy,
         class inout_object_1_t,
         class inout_object_2_t>
void swap_elements(ExecutionPolicy&& exec,
                   inout_object_1_t x,
                   inout_object_2_t y);

[Note: These functions correspond to the BLAS function xSWAP. --end note]

16.9.2.3. Multiply the elements of an object in place by a scalar [linalg.algs.blas1.scal]
template<class Scalar,
         class inout_object_t>
void scale(const Scalar alpha,
           inout_object_t obj);

template<class ExecutionPolicy,
         class Scalar,
         class inout_object_t>
void scale(ExecutionPolicy&& exec,
           const Scalar alpha,
           inout_object_t obj);

[Note: These functions correspond to the BLAS function xSCAL. --end note]

For i... in the domain of obj, the mathematical expression for the algorithm is obj[i...] = alpha * obj[i...].

16.9.2.4. Copy elements of one matrix or vector into another [linalg.algs.blas1.copy]
template<class in_object_t,
         class out_object_t>
void copy(in_object_t x,
          out_object_t y);

template<class ExecutionPolicy,
         class in_object_t,
         class out_object_t>
void copy(ExecutionPolicy&& exec,
          in_object_t x,
          out_object_t y);

[Note: These functions correspond to the BLAS function xCOPY. --end note]

16.9.2.5. Add vectors or matrices elementwise [linalg.algs.blas1.add]
template<class in_object_1_t,
         class in_object_2_t,
         class out_object_t>
void add(in_object_1_t x,
         in_object_2_t y,
         out_object_t z);

template<class ExecutionPolicy,
         class in_object_1_t,
         class in_object_2_t,
         class out_object_t>
void add(ExecutionPolicy&& exec,
         in_object_1_t x,
         in_object_2_t y,
         out_object_t z);

[Note: These functions correspond to the BLAS function xAXPY. --end note]

For i... in the domains of x, y, and z, the mathematical expression for the algorithm is z[i...] = x[i...] + y[i...].

16.9.2.6. Dot product of two vectors [linalg.algs.blas1.dot]
16.9.2.6.1. Nonconjugated dot product of two vectors [linalg.algs.blas1.dot.dotu]

[Note: The functions in this section correspond to the BLAS functions xDOT (for real element types) and xDOTU (for complex element types). --end note]

Nonconjugated dot product with specified result type

template<class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dot(in_vector_1_t v1,
      in_vector_2_t v2,
      T init);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dot(ExecutionPolicy&& exec,
      in_vector_1_t v1,
      in_vector_2_t v2,
      T init);

For N equal to v1.extent(0), the mathematical expression for the algorithm is init = init plus the sum of v1[i] * v2[i] for all i in the domain of v1.

[Note: Like reduce, dot applies binary operator+ in an unspecified order. This may yield a nondeterministic result for non-associative or non-commutative operator+ such as floating-point addition. However, implementations may perform extra work to make the result deterministic. They may do so for all dot overloads, or just for specific ExecutionPolicy types. --end note]

[Note: Users can get xDOTC behavior by giving the first argument as the result of conjugated. Alternately, they can use the shortcut dotc below. --end note]

Nonconjugated dot product with default result type

template<class in_vector_1_t,
         class in_vector_2_t>
auto dot(in_vector_1_t v1,
         in_vector_2_t v2) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t>
auto dot(ExecutionPolicy&& exec,
         in_vector_1_t v1,
         in_vector_2_t v2) -> /* see-below */;
16.9.2.6.2. Conjugated dot product of two vectors [linalg.algs.blas1.dot.dotc]

[Note:

The functions in this section correspond to the BLAS functions xDOT (for real element types) and xDOTC (for complex element types).

dotc exists to give users reasonable default inner product behavior for both real and complex element types.

--end note]

Conjugated dot product with specified result type

template<class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dotc(in_vector_1_t v1,
       in_vector_2_t v2,
       T init);
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class T>
T dotc(ExecutionPolicy&& exec,
       in_vector_1_t v1,
       in_vector_2_t v2,
       T init);

Conjugated dot product with default result type

template<class in_vector_1_t,
         class in_vector_2_t>
auto dotc(in_vector_1_t v1,
          in_vector_2_t v2) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t>
auto dotc(ExecutionPolicy&& exec,
          in_vector_1_t v1,
          in_vector_2_t v2) -> /* see-below */;
16.9.2.7. Scaled sum of squares of a vector’s elements [linalg.algs.blas1.ssq]
template<class T>
struct sum_of_squares_result {
  T scaling_factor;
  T scaled_sum_of_squares;
};
template<class in_vector_t,
         class T>
sum_of_squares_result<T> vector_sum_of_squares(
  in_vector_t v,
  sum_of_squares_result<T> init);
template<class ExecutionPolicy,
         class in_vector_t,
         class T>
sum_of_squares_result<T> vector_sum_of_squares(
  ExecutionPolicy&& exec,
  in_vector_t v,
  sum_of_squares_result<T> init);

[Note: These functions correspond to the LAPACK function xLASSQ. --end note]

16.9.2.8. Euclidean norm of a vector [linalg.algs.blas1.nrm2]
16.9.2.8.1. Euclidean norm with specified result type
template<class in_vector_t,
         class T>
T vector_norm2(in_vector_t v,
               T init);
template<class ExecutionPolicy,
         class in_vector_t,
         class T>
T vector_norm2(ExecutionPolicy&& exec,
               in_vector_t v,
               T init);

[Note: These functions correspond to the BLAS function xNRM2. --end note]

For N equal to v.extent(0), the mathematical expression for the algorithm is sqrt(init + s), where s is the sum of abs(v[i]) * abs(v[i]) for all i in the domain of v. [Note: This does not imply a recommended implementation for floating-point types. See Remarks below. --end note]

[Note: A suggested implementation of this function for floating-point types T would use the scaled_sum_of_squares result from vector_sum_of_squares(x, {.scaling_factor=1.0, .scaled_sum_of_squares=init}). --end note]

16.9.2.8.2. Euclidean norm with default result type
template<class in_vector_t>
auto vector_norm2(in_vector_t v) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_t>
auto vector_norm2(ExecutionPolicy&& exec,
                  in_vector_t v) -> /* see-below */;
16.9.2.9. Sum of absolute values of vector elements [linalg.algs.blas1.asum]
16.9.2.9.1. Sum of absolute values with specified result type
template<class in_vector_t,
         class T>
T vector_abs_sum(in_vector_t v,
                 T init);
template<class ExecutionPolicy,
         class in_vector_t,
         class T>
T vector_abs_sum(ExecutionPolicy&& exec,
                 in_vector_t v,
                 T init);

[Note: This function corresponds to the BLAS functions SASUM, DASUM, CSASUM, and DZASUM. The different behavior for complex element types is based on the observation that this lower-cost approximation of the one-norm serves just as well as the actual one-norm for many linear algebra algorithms in practice. --end note]

For N equal to v.extent(0), the mathematical expression for the algorithm is init plus the sum of abs(v[i]) for all i in the domain of v.

16.9.2.9.2. Sum of absolute values with default result type
template<class in_vector_t>
auto vector_abs_sum(in_vector_t v) -> /* see-below */;
template<class ExecutionPolicy,
         class in_vector_t>
auto vector_abs_sum(ExecutionPolicy&& exec,
                    in_vector_t v) -> /* see-below */;
16.9.2.10. Index of maximum absolute value of vector elements [linalg.algs.blas1.iamax]
template<class in_vector_t>
extents<>::size_type idx_abs_max(in_vector_t v);

template<class ExecutionPolicy,
         class in_vector_t>
extents<>::size_type idx_abs_max(
  ExecutionPolicy&& exec,
  in_vector_t v);

[Note: These functions correspond to the BLAS function IxAMAX. --end note]

16.9.2.11. Frobenius norm of a matrix [linalg.algs.blas1.matfrobnorm]
16.9.2.11.1. Frobenius norm with specified result type
template<class in_matrix_t,
         class T>
T matrix_frob_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_frob_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
16.9.2.11.2. Frobenius norm with default result type
template<class in_matrix_t>
auto matrix_frob_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_frob_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;
16.9.2.12. One norm of a matrix [linalg.algs.blas1.matonenorm]
16.9.2.12.1. One norm with specified result type
template<class in_matrix_t,
         class T>
T matrix_one_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_one_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
16.9.2.12.2. One norm with default result type
template<class in_matrix_t>
auto matrix_one_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_one_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;
16.9.2.13. Infinity norm of a matrix [linalg.algs.blas1.matinfnorm]
16.9.2.13.1. Infinity norm with specified result type
template<class in_matrix_t,
         class T>
T matrix_inf_norm(
  in_matrix_t A,
  T init);
template<class ExecutionPolicy,
         class in_matrix_t,
         class T>
T matrix_inf_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  T init);
16.9.2.13.2. Infinity norm with default result type
template<class in_matrix_t>
auto matrix_inf_norm(
  in_matrix_t A) -> /* see-below */;
template<class ExecutionPolicy,
         class in_matrix_t>
auto matrix_inf_norm(
  ExecutionPolicy&& exec,
  in_matrix_t A) -> /* see-below */;

16.9.3. BLAS 2 functions [linalg.algs.blas2]

16.9.3.1. General matrix-vector product [linalg.algs.blas2.gemv]

[Note: These functions correspond to the BLAS function xGEMV. --end note]

The following requirements apply to all functions in this section.

16.9.3.1.1. Overwriting matrix-vector product
template<class in_vector_t,
         class in_matrix_t,
         class out_vector_t>
void matrix_vector_product(in_matrix_t A,
                           in_vector_t x,
                           out_vector_t y);

template<class ExecutionPolicy,
         class in_vector_t,
         class in_matrix_t,
         class out_vector_t>
void matrix_vector_product(ExecutionPolicy&& exec,
                           in_matrix_t A,
                           in_vector_t x,
                           out_vector_t y);

For i in the domain of y and N equal to A.extent(1), the mathematical expression for the algorithm is y[i] = the sum of A[i,j] * x[j] for all j such that i,j is in the domain of A.

[Example:

constexpr extents<>::size_type num_rows = 5;
constexpr extents<>::size_type num_cols = 6;

// y = 3.0 * A * x
void scaled_matvec_1(
  mdspan<double, extents<num_rows, num_cols>> A,
  mdspan<double, extents<num_cols>> x,
  mdspan<double, extents<num_rows>> y)
{
  matrix_vector_product(scaled(3.0, A), x, y);
}

// y = 3.0 * A * x + 2.0 * y
void scaled_matvec_2(
  mdspan<double, extents<num_rows, num_cols>> A,
  mdspan<double, extents<num_cols>> x,
  mdspan<double, extents<num_rows>> y)
{
  matrix_vector_product(scaled(3.0, A), x,
                        scaled(2.0, y), y);
}

// z = 7.0 times the transpose of A, times y
void scaled_matvec_2(mdspan<double, extents<num_rows, num_cols>> A,
  mdspan<double, extents<num_rows>> y,
  mdspan<double, extents<num_cols>> z)
{
  matrix_vector_product(scaled(7.0, transposed(A)), y, z);
}
--end example]
16.9.3.1.2. Updating matrix-vector product
template<class in_vector_1_t,
         class in_matrix_t,
         class in_vector_2_t,
         class out_vector_t>
void matrix_vector_product(in_matrix_t A,
                           in_vector_1_t x,
                           in_vector_2_t y,
                           out_vector_t z);

template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_matrix_t,
         class in_vector_2_t,
         class out_vector_t>
void matrix_vector_product(ExecutionPolicy&& exec,
                           in_matrix_t A,
                           in_vector_1_t x,
                           in_vector_2_t y,
                           out_vector_t z);

For i in the domain of z and N equal to A.extent(1), the mathematical expression for the algorithm is z[i] = y[i] + A[i,j] * x[j] for all j such that i,j is in the domain of A.

16.9.3.2. Symmetric matrix-vector product [linalg.algs.blas2.symv]

[Note: These functions correspond to the BLAS functions xSYMV and xSPMV. --end note]

The following requirements apply to all functions in this section.

16.9.3.2.1. Overwriting symmetric matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void symmetric_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void symmetric_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);

For i in the domain of y, the mathematical expression for the algorithm is y[i] = the sum of A[i,j] * x[j] for all j in the triangle of A specified by t, plus the sum of A[j,i] * x[j] for all j not equal to i such that j,i is in the domain of A but not in the triangle of A specified by t.

16.9.3.2.2. Updating symmetric matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void symmetric_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  in_vector_1_t x,
  in_vector_2_t y,
  out_vector_t z);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void symmetric_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  in_vector_1_t x,
  in_vector_2_t y,
  out_vector_t z);

For i in the domain of y, the mathematical expression for the algorithm is z[i] = y[i] plus the sum of A[i,j] * x[j] for all j in the triangle of A specified by t, plus the sum of A[j,i] * x[j] for all j not equal to i such that j,i is in the domain of A but not in the triangle of A specified by t.

16.9.3.3. Hermitian matrix-vector product [linalg.algs.blas2.hemv]

[Note: These functions correspond to the BLAS functions xHEMV and xHPMV. --end note]

The following requirements apply to all functions in this section.

16.9.3.3.1. Overwriting Hermitian matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void hermitian_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void hermitian_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_t x,
                                     out_vector_t y);

For i in the domain of y, the mathematical expression for the algorithm is y[i] = the sum of A[i,j] * x[j] for all j in the triangle of A specified by t, plus the sum of conj(A[j,i]) * x[j] for all j not equal to i such that j,i is in the domain of A but not in the triangle of A specified by t.

16.9.3.3.2. Updating Hermitian matrix-vector product
template<class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void hermitian_matrix_vector_product(in_matrix_t A,
                                     Triangle t,
                                     in_vector_1_t x,
                                     in_vector_2_t y,
                                     out_vector_t z);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void hermitian_matrix_vector_product(ExecutionPolicy&& exec,
                                     in_matrix_t A,
                                     Triangle t,
                                     in_vector_1_t x,
                                     in_vector_2_t y,
                                     out_vector_t z);

For i in the domain of y, the mathematical expression for the algorithm is z[i] = y[i] plus the sum of A[i,j] * x[j] for all j in the triangle of A specified by t, plus the sum of conj(A[j,i]) * x[j] for all j not equal to i such that j,i is in the domain of A but not in the triangle of A specified by t.

16.9.3.4. Triangular matrix-vector product [linalg.algs.blas2.trmv]

[Note: These functions correspond to the BLAS functions xTRMV and xTPMV. --end note]

The following requirements apply to all functions in this section.

16.9.3.4.1. Overwriting triangular matrix-vector product [linalg.algs.blas2.trmv.ov]
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t x,
  out_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t x,
  out_vector_t y);

For i in the domain of y, the mathematical expression for the algorithm is y[i] = the sum of A[i,j] * x[j] for all j in the subset of the domain of A specified by t and d.

16.9.3.4.2. In-place triangular matrix-vector product [linalg.algs.blas2.trmv.in-place]
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_product(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t y);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_product(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t y);

[Note:

Performing this operation in place hinders parallelization. However, other ExecutionPolicy-specific optimizations, such as vectorization, are still possible. This is why the ExecutionPolicy overload exists.

--end note]

For i in the domain of y, the mathematical expression for the algorithm is y[i] = the sum of A[i,j] * y[j] for all j in the subset of the domain of A specified by t and d.

16.9.3.4.3. Updating triangular matrix-vector product [linalg.algs.blas2.trmv.up]
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void triangular_matrix_vector_product(in_matrix_t A,
                                      Triangle t,
                                      DiagonalStorage d,
                                      in_vector_1_t x,
                                      in_vector_2_t y,
                                      out_vector_t z);

template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_1_t,
         class in_vector_2_t,
         class out_vector_t>
void triangular_matrix_vector_product(ExecutionPolicy&& exec,
                                      in_matrix_t A,
                                      Triangle t,
                                      DiagonalStorage d,
                                      in_vector_1_t x,
                                      in_vector_2_t y,
                                      out_vector_t z);

For i in the domain of y, the mathematical expression for the algorithm is z[i] = y[i] plus the sum of A[i,j] * x[j] for all j in the subset of the domain of A specified by t and d.

16.9.3.5. Solve a triangular linear system [linalg.algs.blas2.trsv]

[Note: These functions correspond to the BLAS functions xTRSV and xTPSV. --end note]

The following requirements apply to all functions in this section.

16.9.3.5.1. Not-in-place triangular solve [linalg.algs.blas2.trsv.not-in-place]
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_solve(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t b,
  out_vector_t x);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class in_vector_t,
         class out_vector_t>
void triangular_matrix_vector_solve(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  in_vector_t b,
  out_vector_t x);

If DiagonalStorage is explicit_diagonal_t, then for i in the domain of x, the mathematical expression for the algorithm is x[i] = b[i] - s / A[i,i], where s is the sum of A[i,j] * x[j] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i in the domain of x, the mathematical expression for the algorithm is x[i] = b[i] - s, where s is the sum of A[i,j] * x[j] for all j not equal to i in the subset of the domain of A specified by t and d.

16.9.3.5.2. In-place triangular solve [linalg.algs.blas2.trsv.in-place]
template<class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_solve(
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t b);
template<class ExecutionPolicy,
         class in_matrix_t,
         class Triangle,
         class DiagonalStorage,
         class inout_vector_t>
void triangular_matrix_vector_solve(
  ExecutionPolicy&& exec,
  in_matrix_t A,
  Triangle t,
  DiagonalStorage d,
  inout_vector_t b);

[Note:

Performing triangular solve in place hinders parallelization. However, other ExecutionPolicy-specific optimizations, such as vectorization, are still possible. This is why the ExecutionPolicy overload exists.

--end note]

If DiagonalStorage is explicit_diagonal_t, then for i in the domain of x, the mathematical expression for the algorithm is b[i] = b[i] - s / A[i,i], where s is the sum of A[i,j] * b[j] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i in the domain of x, the mathematical expression for the algorithm is b[i] = b[i] - s, where s is the sum of A[i,j] * b[j] for all j not equal to i in the subset of the domain of A specified by t and d.

16.9.3.6. Rank-1 (outer product) update of a matrix [linalg.algs.blas2.rank1]
16.9.3.6.1. Nonsymmetric nonconjugated rank-1 update [linalg.algs.blas2.rank1.geru]
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

[Note: This function corresponds to the BLAS functions xGER (for real element types) and xGERU (for complex element types). --end note]

For i,j in the domain of A, the mathematical expression for the algorithm is A[i,j] += x[i] * y[j].

[Note: Users can get xGERC behavior by giving the second argument as the result of conjugated. Alternately, they can use the shortcut matrix_rank_1_update_c below. --end note]

16.9.3.6.2. Nonsymmetric conjugated rank-1 update [linalg.algs.blas2.rank1.gerc]
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update_c(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t>
void matrix_rank_1_update_c(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A);

[Note: This function corresponds to the BLAS functions xGER (for real element types) and xGERC (for complex element types). --end note]

16.9.3.6.3. Rank-1 update of a Symmetric matrix [linalg.algs.blas2.rank1.syr]
template<class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);

[Note:

These functions correspond to the BLAS functions xSYR and xSPR.

They have overloads taking a scaling factor alpha, because it would be impossible to express updates like C = C - x x^T otherwise.

--end note]

For i,j in the domain of A and in the triangle of A specified by t, the mathematical expression for the algorithm is A[i,j] += x[i] * x[j] for overloads without an alpha parameter, and A[i,j] += alpha * x[i] * x[j] for overloads with an alpha parameter.

16.9.3.6.4. Rank-1 update of a Hermitian matrix [linalg.algs.blas2.rank1.her]
template<class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_vector_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_1_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_vector_t x,
  inout_matrix_t A,
  Triangle t);

[Note:

These functions correspond to the BLAS functions xHER and xHPR.

They have overloads taking a scaling factor alpha, because it would be impossible to express the update A = A - x x^H otherwise.

--end note]

For i,j in the domain of A and in the triangle of A specified by t, the mathematical expression for the algorithm is A[i,j] += x[i] * conj(x[j]) for overloads without an alpha parameter, and A[i,j] += alpha * x[i] * conj(x[j]) for overloads without an alpha parameter.

16.9.3.7. Rank-2 update of a symmetric matrix [linalg.algs.blas2.rank2.syr2]
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

[Note: These functions correspond to the BLAS functions xSYR2 and xSPR2. --end note]

For i,j in the domain of A and in the triangle of A specified by t, the mathematical expression for the algorithm is A[i,j] += x[i] * y[j] + y[i] * x[j].

16.9.3.8. Rank-2 update of a Hermitian matrix [linalg.algs.blas2.rank2.her2]
template<class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2_update(
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

template<class ExecutionPolicy,
         class in_vector_1_t,
         class in_vector_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2_update(
  ExecutionPolicy&& exec,
  in_vector_1_t x,
  in_vector_2_t y,
  inout_matrix_t A,
  Triangle t);

[Note: These functions correspond to the BLAS functions xHER2 and xHPR2. --end note]

For i,j in the domain of A and in the triangle of A specified by t, the mathematical expression for the algorithm is A[i,j] += x[i] * conj(y[j]) + y[i] * conj(x[j]).

16.9.4. BLAS 3 functions [linalg.algs.blas3]

16.9.4.1. General matrix-matrix product [linalg.algs.blas3.gemm]

[Note: These functions correspond to the BLAS function xGEMM. --end note]

The following requirements apply to all functions in this section.

16.9.4.1.1. Overwriting general matrix-matrix product
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class out_matrix_t>
void matrix_product(in_matrix_1_t A,
                    in_matrix_2_t B,
                    out_matrix_t C);

template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class out_matrix_t>
void matrix_product(ExecutionPolicy&& exec,
                    in_matrix_1_t A,
                    in_matrix_2_t B,
                    out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = the sum of A[i,k] * B[k,j] for all k such that i,k is in the domain of A.

16.9.4.1.2. Updating general matrix-matrix product
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void matrix_product(in_matrix_1_t A,
                    in_matrix_2_t B,
                    in_matrix_3_t E,
                    out_matrix_t C);

template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void matrix_product(ExecutionPolicy&& exec,
                    in_matrix_1_t A,
                    in_matrix_2_t B,
                    in_matrix_3_t E,
                    out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] plus the sum of A[i,k] * B[k,j] for all k such that i,k is in the domain of A.

16.9.4.2. Symmetric matrix-matrix product [linalg.algs.blas3.symm]

[Note:

These functions correspond to the BLAS function xSYMM.

Unlike the symmetric rank-1 or rank-k update functions, these functions assume that the input matrix A -- not the output matrix -- is symmetric.

--end note]

The following requirements apply to all functions in this section.

The following requirements apply to all overloads of symmetric_matrix_left_product.

The following requirements apply to all overloads of symmetric_matrix_right_product.

16.9.4.2.1. Overwriting symmetric matrix-matrix left product [linalg.algs.blas3.symm.ov.left]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = A[i,i] * B[i,j] plus the sum of A[i,k1] * B[k1,j] for all k1 not equal to i such that i,k1 is in the domain of A and in the triangle of A specified by t, plus the sum of A[k2,i] * B[k2,j] for all k2 not equal to i such that k2,i is in the domain of A and in the triangle of A specified by t.

16.9.4.2.2. Overwriting symmetric matrix-matrix right product [linalg.algs.blas3.symm.ov.right]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = B[i,j] * A[i,i] plus the sum of B[i,k1] * A[k1,j] for all k1 not equal to j such that k1,j is in the domain of A and in the triangle of A specified by t, plus the sum of B[i,k2] * A[j,k2] for all k2 not equal to j such that k2,j is in the domain of A and in the triangle of A specified by t.

16.9.4.2.3. Updating symmetric matrix-matrix left product [linalg.algs.blas3.symm.up.left]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] + A[i,i] * B[i,j] plus the sum of A[i,k1] * B[k1,j] for all k1 not equal to i such that i,k1 is in the domain of A and in the triangle of A specified by t, plus the sum of A[k2,i] * B[k2,j] for all k2 not equal to i such that k2,i is in the domain of A and in the triangle of A specified by t.

16.9.4.2.4. Updating symmetric matrix-matrix right product [linalg.algs.blas3.symm.up.right]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void symmetric_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] + B[i,j] * A[i,i] plus the sum of B[i,k1] * A[k1,j] for all k1 not equal to j such that k1,j is in the domain of A and in the triangle of A specified by t, plus the sum of B[i,k2] * A[j,k2] for all k2 not equal to j such that k2,j is in the domain of A and in the triangle of A specified by t.

16.9.4.3. Hermitian matrix-matrix product [linalg.algs.blas3.hemm]

[Note:

These functions correspond to the BLAS function xHEMM.

Unlike the Hermitian rank-1 or rank-k update functions, these functions assume that the input matrix -- not the output matrix -- is Hermitian.

--end note]

The following requirements apply to all functions in this section.

The following requirements apply to all overloads of hermitian_matrix_left_product.

The following requirements apply to all overloads of hermitian_matrix_right_product.

16.9.4.3.1. Overwriting Hermitian matrix-matrix left product [linalg.algs.blas3.hemm.ov.left]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = A[i,i] * B[i,j] plus the sum of A[i,k1] * B[k1,j] for all k1 not equal to i such that i,k1 is in the domain of A and in the triangle of A specified by t, plus the sum of conj(A[k2,i]) * B[k2,j] for all k2 not equal to i such that k2,i is in the domain of A and in the triangle of A specified by t.

16.9.4.3.2. Overwriting Hermitian matrix-matrix right product [linalg.algs.blas3.hemm.ov.right]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = B[i,j] * A[i,i] plus the sum of B[i,k1] * A[k1,j] for all k1 not equal to j such that k1,j is in the domain of A and in the triangle of A specified by t, plus the sum of B[i,k2] * conj(A[j,k2]) for all k2 not equal to j such that k2,j is in the domain of A and in the triangle of A specified by t.

16.9.4.3.3. Updating Hermitian matrix-matrix left product [linalg.algs.blas3.hemm.up.left]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] + A[i,i] * B[i,j] plus the sum of A[i,k1] * B[k1,j] for all k1 not equal to i such that i,k1 is in the domain of A and in the triangle of A specified by t, plus the sum of conj(A[k2,i]) * B[k2,j] for all k2 not equal to i such that k2,i is in the domain of A and in the triangle of A specified by t.

16.9.4.3.4. Updating Hermitian matrix-matrix right product [linalg.algs.blas3.hemm.up.right]
template<class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void hermitian_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] + B[i,j] * A[i,i] plus the sum of B[i,k1] * A[k1,j] for all k1 not equal to j such that k1,j is in the domain of A and in the triangle of A specified by t, plus the sum of B[i,k2] * conj(A[j,k2]) for all k2 not equal to j such that k2,j is in the domain of A and in the triangle of A specified by t.

16.9.4.4. Triangular matrix-matrix product [linalg.algs.blas3.trmm]

[Note: These functions correspond to the BLAS function xTRMM. --end note]

The following requirements apply to all functions in this section.

The following requirements apply to all overloads of triangular_matrix_left_product.

The following requirements apply to all overloads of triangular_matrix_right_product.

16.9.4.4.1. Overwriting triangular matrix-matrix left product [linalg.algs.blas3.trmm.ov.left]

Not-in-place overwriting triangular matrix-matrix left product

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = the sum of A[i,k] * B[k,j] for all k such that i,k is in the domain of A and in the triangle of A specified by t and d.

In-place overwriting triangular matrix-matrix left product

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = the sum of A[i,k] * C[k,j] for all k such that i,k is in the domain of A and in the triangle of A specified by t and d.

16.9.4.4.2. Overwriting triangular matrix-matrix right product [linalg.algs.blas3.trmm.ov.right]

Not-in-place overwriting triangular matrix-matrix right product

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = the sum of B[i,k] * A[k,j] for all k such that k,j is in the domain of A and in the triangle of A specified by t and d.

In-place overwriting triangular matrix-matrix right product

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = the sum of C[i,k] * A[k,j] for all k such that k,j is in the domain of A and in the triangle of A specified by t and d.

16.9.4.4.3. Updating triangular matrix-matrix left product [linalg.algs.blas3.trmm.up.left]
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_left_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] plus the sum of A[i,k] * B[k,j] for all k such that i,k is in the domain of A and in the triangle of A specified by t and d.

16.9.4.4.4. Updating triangular matrix-matrix right product [linalg.algs.blas3.trmm.up.right]
template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class in_matrix_3_t,
         class out_matrix_t>
void triangular_matrix_right_product(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  in_matrix_3_t E,
  out_matrix_t C);

For i,j in the domain of C, the mathematical expression for the algorithm is C[i,j] = E[i,j] plus the sum of B[i,k] * A[k,j] for all k such that k,j is in the domain of A and in the triangle of A specified by t and d.

16.9.4.5. Rank-k update of a symmetric or Hermitian matrix [linalg.alg.blas3.rank-k]

[Note: Users can achieve the effect of the TRANS argument of these BLAS functions, by applying transposed or conjugate_transposed to the input matrix. --end note]

16.9.4.5.1. Rank-k symmetric matrix update [linalg.alg.blas3.rank-k.syrk]
template<class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_k_update(
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_k_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);

[Note:

These functions correspond to the BLAS function xSYRK.

They take a scaling factor alpha, because it would be impossible to express the update C = C - A A^T otherwise. The scaling factor parameter is required in order to avoid ambiguity with ExecutionPolicy.

--end note]

For i,j in the domain of C and in the triangle of C specified by t, the mathematical expression for the algorithm is C[i,j] = C[i,j] plus the sum of alpha * A[i,k] * A[j,k] for all k such that i,k is in the domain of A.

16.9.4.5.2. Rank-k Hermitian matrix update [linalg.alg.blas3.rank-k.herk]
template<class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_k_update(
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class T,
         class in_matrix_1_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_k_update(
  ExecutionPolicy&& exec,
  T alpha,
  in_matrix_1_t A,
  inout_matrix_t C,
  Triangle t);

[Note:

These functions correspond to the BLAS function xHERK.

They take a scaling factor alpha, because it would be impossible to express the updates C = C - A A^T or C = C - A A^H otherwise. The scaling factor parameter is required in order to avoid ambiguity with ExecutionPolicy.

--end note]

For i,j in the domain of C and in the triangle of C specified by t, the mathematical expression for the algorithm is C[i,j] = C[i,j] plus the sum of alpha * A[i,k] * conj(A[j,k]) for all k such that i,k is in the domain of A.

16.9.4.6. Rank-2k update of a symmetric or Hermitian matrix [linalg.alg.blas3.rank2k]

[Note: Users can achieve the effect of the TRANS argument of these BLAS functions, by applying transposed or conjugate_transposed to the input matrices. --end note]

16.9.4.6.1. Rank-2k symmetric matrix update [linalg.alg.blas3.rank2k.syr2k]
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2k_update(
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void symmetric_matrix_rank_2k_update(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);

[Note: These functions correspond to the BLAS function xSYR2K. The BLAS "quick reference" has a typo; the "ALPHA" argument of CSYR2K and ZSYR2K should not be conjugated. --end note]

For i,j in the domain of C and in the triangle of C specified by t, the mathematical expression for the algorithm is C[i,j] = C[i,j] plus the sum of A[i,k1] * B[j,k1] for all k1 such that i,k1 is in the domain of A, plus the sum of B[i,k2] * A[j,k2] for all k2 such that i,k2 is in the domain of B.

16.9.4.6.2. Rank-2k Hermitian matrix update [linalg.alg.blas3.rank2k.her2k]
template<class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2k_update(
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);

template<class ExecutionPolicy,
         class in_matrix_1_t,
         class in_matrix_2_t,
         class inout_matrix_t,
         class Triangle>
void hermitian_matrix_rank_2k_update(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  in_matrix_2_t B,
  inout_matrix_t C,
  Triangle t);

[Note: These functions correspond to the BLAS function xHER2K. --end note]

For i,j in the domain of C and in the triangle of C specified by t, the mathematical expression for the algorithm is C[i,j] = C[i,j] plus the sum of A[i,k1] * conj(B[j,k1]) for all k1 such that i,k1 is in the domain of A, plus the sum of B[i,k2] * conj(A[j,k2]) for all k2 such that i,k2 is in the domain of B.

16.9.4.7. Solve multiple triangular linear systems [linalg.alg.blas3.trsm]

[Note: These functions correspond to the BLAS function xTRSM. The Reference BLAS does not have a xTPSM function. --end note]

The following requirements apply to all functions in this section.

16.9.4.7.1. Solve multiple triangular linear systems with triangular matrix on the left [linalg.alg.blas3.trsm.left]

Not-in-place left solve of multiple triangular systems

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_left_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_left_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);

If DiagonalStorage is explicit_diagonal_t, then for i,k in the domain of X, the mathematical expression for the algorithm is X[i,k] = B[i,k] - s / A[i,i], where s is the sum of A[i,j] * X[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i,k in the domain of X, then the mathematical expression for the algorithm is X[i,k] = B[i,k] - s, where s is the sum of A[i,j] * X[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

In-place left solve of multiple triangular systems

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_left_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_left_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);

[Note:

This algorithm makes it possible to compute factorizations like Cholesky and LU in place.

Performing triangular solve in place hinders parallelization. However, other ExecutionPolicy-specific optimizations, such as vectorization, are still possible. This is why the ExecutionPolicy overload exists.

--end note]

If DiagonalStorage is explicit_diagonal_t, then for i,k in the domain of B, the mathematical expression for the algorithm is B[i,k] = B[i,k] - s / A[i,i], where s is the sum of A[i,j] * B[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i,k in the domain of B, then the mathematical expression for the algorithm is B[i,k] = B[i,k] - s, where s is the sum of A[i,j] * B[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

16.9.4.7.2. Solve multiple triangular linear systems with triangular matrix on the right [linalg.alg.blas3.trsm.right]

Not-in-place right solve of multiple triangular systems

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_right_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class in_matrix_2_t,
         class out_matrix_t>
void triangular_matrix_matrix_right_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  in_matrix_2_t B,
  out_matrix_t X);

If DiagonalStorage is explicit_diagonal_t, then for i,k in the domain of X, the mathematical expression for the algorithm is X[i,k] = B[i,k] - s / A[i,i], where s is the sum of X[i,j] * A[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i,k in the domain of X, then the mathematical expression for the algorithm is X[i,k] = B[i,k] - s, where s is the sum of X[i,j] * A[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

In-place right solve of multiple triangular systems

template<class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_right_solve(
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);
template<class ExecutionPolicy,
         class in_matrix_1_t,
         class Triangle,
         class DiagonalStorage,
         class inout_matrix_t>
void triangular_matrix_matrix_right_solve(
  ExecutionPolicy&& exec,
  in_matrix_1_t A,
  Triangle t,
  DiagonalStorage d,
  inout_matrix_t B);

[Note:

This algorithm makes it possible to compute factorizations like Cholesky and LU in place.

Performing triangular solve in place hinders parallelization. However, other ExecutionPolicy-specific optimizations, such as vectorization, are still possible. This is why the ExecutionPolicy overload exists.

--end note]

If DiagonalStorage is explicit_diagonal_t, then for i,k in the domain of B, the mathematical expression for the algorithm is B[i,k] = B[i,k] - s / A[i,i], where s is the sum of B[i,j] * A[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

If DiagonalStorage is implicit_unit_diagonal_t, then for i,k in the domain of B, then the mathematical expression for the algorithm is B[i,k] = B[i,k] - s, where s is the sum of B[i,j] * A[j,k] for all j not equal to i in the subset of the domain of A specified by t and d.

17. Examples

17.1. Cholesky factorization

This example shows how to compute the Cholesky factorization of a real symmetric positive definite matrix A stored as an mdspan with a unique non-packed layout. The algorithm imitates DPOTRF2 in LAPACK 3.9.0. If Triangle is upper_triangle_t, then it computes the Cholesky factorization A = U^T U. Otherwise, it computes the Cholesky factorization A = L L^T. The function returns 0 if success, else k+1 if row/column k has a zero or NaN (not a number) diagonal entry.

#include <linalg>
#include <cmath>

template<class inout_matrix_t,
         class Triangle>
int cholesky_factor(inout_matrix_t A, Triangle t)
{
  using element_type = typename inout_matrix_t::element_type;
  constexpr element_type ZERO {};
  constexpr element_type ONE (1.0);
  const auto n = A.extent(0);

  if (n == 0) {
    return 0;
  }
  else if (n == 1) {
    if (A[0,0] <= ZERO || isnan(A[0,0])) {
      return 1;
    }
    A[0,0] = sqrt(A[0,0]);
  }
  else {
    // Partition A into [A11, A12,
    //                   A21, A22],
    // where A21 is the transpose of A12.
    const extents<>::size_type n1 = n / 2;
    const extents<>::size_type n2 = n - n1;
    auto A11 = submdspan(A, pair{0, n1}, pair{0, n1});
    auto A22 = submdspan(A, pair{n1, n}, pair{n1, n});

    // Factor A11
    const int info1 = cholesky_factor(A11, t);
    if (info1 != 0) {
      return info1;
    }

    using std::linalg::symmetric_matrix_rank_k_update;
    using std::linalg::transposed;
    if constexpr (std::is_same_v<Triangle, upper_triangle_t>) {
      // Update and scale A12
      auto A12 = submdspan(A, pair{0, n1}, pair{n1, n});
      using std::linalg::triangular_matrix_matrix_left_solve;
      triangular_matrix_matrix_left_solve(transposed(A11),
        upper_triangle, explicit_diagonal, A12);
      // A22 = A22 - A12^T * A12
      symmetric_matrix_rank_k_update(-ONE, transposed(A12),
                                      A22, t);
    }
    else {
      //
      // Compute the Cholesky factorization A = L * L^T
      //
      // Update and scale A21
      auto A21 = submdspan(A, pair{n1, n}, pair{0, n1});
      using std::linalg::triangular_matrix_matrix_right_solve;
      triangular_matrix_matrix_right_solve(transposed(A11),
        lower_triangle, explicit_diagonal, A21);
      // A22 = A22 - A21 * A21^T
      symmetric_matrix_rank_k_update(-ONE, A21, A22, t);
    }

    // Factor A22
    const int info2 = cholesky_factor(A22, t);
    if (info2 != 0) {
      return info2 + n1;
    }
  }
}

17.2. Solve linear system using Cholesky factorization

This example shows how to solve a symmetric positive definite linear system Ax=b, using the Cholesky factorization computed in the previous example in-place in the matrix A. The example assumes that cholesky_factor(A, t) returned 0, indicating no zero or NaN pivots.

template<class in_matrix_t,
         class Triangle,
         class in_vector_t,
         class out_vector_t>
void cholesky_solve(
  in_matrix_t A,
  Triangle t,
  in_vector_t b,
  out_vector_t x)
{
  using std::linalg::transposed;
  using std::linalg::triangular_matrix_vector_solve;

  if constexpr (std::is_same_v<Triangle, upper_triangle_t>) {
    // Solve Ax=b where A = U^T U
    //
    // Solve U^T c = b, using x to store c.
    triangular_matrix_vector_solve(transposed(A), t,
                                   explicit_diagonal, b, x);
    // Solve U x = c, overwriting x with result.
    triangular_matrix_vector_solve(A, t, explicit_diagonal, x);
  }
  else {
    // Solve Ax=b where A = L L^T
    //
    // Solve L c = b, using x to store c.
    triangular_matrix_vector_solve(A, t, explicit_diagonal, b, x);
    // Solve L^T x = c, overwriting x with result.
    triangular_matrix_vector_solve(transposed(A), t,
                                   explicit_diagonal, x);
  }
}

17.3. Compute QR factorization of a tall skinny matrix

This example shows how to compute the QR factorization of a "tall and skinny" matrix V, using a cache-blocked algorithm based on rank-k symmetric matrix update and Cholesky factorization. "Tall and skinny" means that the matrix has many more rows than columns.

// Compute QR factorization A = Q R, with A storing Q.
template<class inout_matrix_t,
         class out_matrix_t>
int cholesky_tsqr_one_step(
  inout_matrix_t A, // A on input, Q on output
  out_matrix_t R)
{
  // One might use cache size, sizeof(element_type), and A.extent(1)
  // to pick the number of rows per block.  For now, we just pick
  // some constant.
  constexpr extents<>::size_type max_num_rows_per_block = 500;

  using R_element_type = typename out_matrix_t::element_type;
  constexpr R_element_type ZERO {};
  for(extents<>::size_type i = 0; i < R.extent(0); ++i) {
    for(extents<>::size_type j = 0; j < R.extent(1); ++j) {
      R[0,0] = ZERO;
    }
  }

  // Cache-blocked version of R = R + A^T * A.
  const auto num_rows = A.extent(0);
  auto rest_num_rows = num_rows;
  auto A_rest = A;
  while(A_rest.extent(0) > 0) {
    const ptrdiff num_rows_per_block =
      min(A.extent(0), max_num_rows_per_block);
    auto A_cur = submdspan(A_rest, pair{0, num_rows_per_block}, full_extent);
    A_rest = submdspan(A_rest,
      pair{num_rows_per_block, A_rest.extent(0)}, full_extent);
    // R = R + A_cur^T * A_cur
    using std::linalg::symmetric_matrix_rank_k_update;
    constexpr R_element_type ONE(1.0);
    symmetric_matrix_rank_k_update(ONE, transposed(A_cur),
                                   R, upper_triangle);
  }

  const int info = cholesky_factor(R, upper_triangle);
  if(info != 0) {
    return info;
  }
  using std::linalg::triangular_matrix_matrix_left_solve;
  triangular_matrix_matrix_left_solve(R, upper_triangle, A);
  return info;
}

// Compute QR factorization A = Q R.  Use R_tmp as temporary R factor
// storage for iterative refinement.
template<class in_matrix_t,
         class out_matrix_1_t,
         class out_matrix_2_t,
         class out_matrix_3_t>
int cholesky_tsqr(
  in_matrix_t A,
  out_matrix_1_t Q,
  out_matrix_2_t R_tmp,
  out_matrix_3_t R)
{
  assert(R.extent(0) == R.extent(1));
  assert(A.extent(1) == R.extent(0));
  assert(R_tmp.extent(0) == R_tmp.extent(1));
  assert(A.extent(0) == Q.extent(0));
  assert(A.extent(1) == Q.extent(1));

  copy(A, Q);
  const int info1 = cholesky_tsqr_one_step(Q, R);
  if(info1 != 0) {
    return info1;
  }
  // Use one step of iterative refinement to improve accuracy.
  const int info2 = cholesky_tsqr_one_step(Q, R_tmp);
  if(info2 != 0) {
    return info2;
  }
  // R = R_tmp * R
  using std::linalg::triangular_matrix_left_product;
  triangular_matrix_left_product(R_tmp, upper_triangle,
                                 explicit_diagonal, R);
  return 0;
}