29 Numerics library [numerics]

29.9 Basic linear algebra algorithms [linalg]

29.9.14 BLAS 2 algorithms [linalg.algs.blas2]

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

[Note 1: 
These functions correspond to the BLAS function xGEMV.
— end note]
The following elements apply to all functions in [linalg.algs.blas2.gemv].
Mandates:
  • possibly-multipliable<decltype(A), decltype(x), decltype(y)>() is true, and
  • possibly-addable<decltype(x), decltype(y), decltype(z)>() is true for those overloads that take a z parameter.
Preconditions:
  • multipliable(A,x,y) is true, and
  • addable(x,y,z) is true for those overloads that take a z parameter.
Complexity: .
template<in-matrix InMat, in-vector InVec, out-vector OutVec> void matrix_vector_product(InMat A, InVec x, OutVec y); template<class ExecutionPolicy, in-matrix InMat, in-vector InVec, out-vector OutVec> void matrix_vector_product(ExecutionPolicy&& exec, InMat A, InVec x, OutVec y);
These functions perform an overwriting matrix-vector product.
Effects: Computes .
[Example 1: constexpr size_t num_rows = 5; constexpr size_t num_cols = 6; // y = 3.0 * A * x void scaled_matvec_1(mdspan<double, extents<size_t, num_rows, num_cols>> A, mdspan<double, extents<size_t, num_cols>> x, mdspan<double, extents<size_t, num_rows>> y) { matrix_vector_product(scaled(3.0, A), x, y); } // z = 7.0 times the transpose of A, times y void scaled_transposed_matvec(mdspan<double, extents<size_t, num_rows, num_cols>> A, mdspan<double, extents<size_t, num_rows>> y, mdspan<double, extents<size_t, num_cols>> z) { matrix_vector_product(scaled(7.0, transposed(A)), y, z); } — end example]
template<in-matrix InMat, in-vector InVec1, in-vector InVec2, out-vector OutVec> void matrix_vector_product(InMat A, InVec1 x, InVec2 y, OutVec z); template<class ExecutionPolicy, in-matrix InMat, in-vector InVec1, in-vector InVec2, out-vector OutVec> void matrix_vector_product(ExecutionPolicy&& exec, InMat A, InVec1 x, InVec2 y, OutVec z);
These functions performs an updating matrix-vector product.
Effects: Computes .
Remarks: z may alias y.
[Example 2: // y = 3.0 * A * x + 2.0 * y void scaled_matvec_2(mdspan<double, extents<size_t, num_rows, num_cols>> A, mdspan<double, extents<size_t, num_cols>> x, mdspan<double, extents<size_t, num_rows>> y) { matrix_vector_product(scaled(3.0, A), x, scaled(2.0, y), y); } — end example]

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

[Note 1: 
These functions correspond to the BLAS functions xSYMV and xSPMV[bib].
— end note]
The following elements apply to all functions in [linalg.algs.blas2.symv].
Mandates:
  • If InMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true;
  • possibly-multipliable<decltype(A), decltype(x), decltype(y)>() is true; and
  • possibly-addable<decltype(x), decltype(y), decltype(z)>() is true for those overloads that take a z parameter.
Preconditions:
  • A.extent(0) equals A.extent(1),
  • multipliable(A,x,y) is true, and
  • addable(x,y,z) is true for those overloads that take a z parameter.
Complexity: .
template<in-matrix InMat, class Triangle, in-vector InVec, out-vector OutVec> void symmetric_matrix_vector_product(InMat A, Triangle t, InVec x, OutVec y); template<class ExecutionPolicy, in-matrix InMat, class Triangle, in-vector InVec, out-vector OutVec> void symmetric_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, InVec x, OutVec y);
These functions perform an overwriting symmetric matrix-vector product, taking into account the Triangle parameter that applies to the symmetric matrix A ([linalg.general]).
Effects: Computes .
template<in-matrix InMat, class Triangle, in-vector InVec1, in-vector InVec2, out-vector OutVec> void symmetric_matrix_vector_product(InMat A, Triangle t, InVec1 x, InVec2 y, OutVec z); template<class ExecutionPolicy, in-matrix InMat, class Triangle, in-vector InVec1, in-vector InVec2, out-vector OutVec> void symmetric_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, InVec1 x, InVec2 y, OutVec z);
These functions perform an updating symmetric matrix-vector product, taking into account the Triangle parameter that applies to the symmetric matrix A ([linalg.general]).
Effects: Computes .
Remarks: z may alias y.

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

[Note 1: 
These functions correspond to the BLAS functions xHEMV and xHPMV[bib].
— end note]
The following elements apply to all functions in [linalg.algs.blas2.hemv].
Mandates:
  • If InMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true;
  • possibly-multipliable<decltype(A), decltype(x), decltype(y)>() is true; and
  • possibly-addable<decltype(x), decltype(y), decltype(z)>() is true for those overloads that take a z parameter.
Preconditions:
  • A.extent(0) equals A.extent(1),
  • multipliable(A, x, y) is true, and
  • addable(x, y, z) is true for those overloads that take a z parameter.
Complexity: .
template<in-matrix InMat, class Triangle, in-vector InVec, out-vector OutVec> void hermitian_matrix_vector_product(InMat A, Triangle t, InVec x, OutVec y); template<class ExecutionPolicy, in-matrix InMat, class Triangle, in-vector InVec, out-vector OutVec> void hermitian_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, InVec x, OutVec y);
These functions perform an overwriting Hermitian matrix-vector product, taking into account the Triangle parameter that applies to the Hermitian matrix A ([linalg.general]).
Effects: Computes .
template<in-matrix InMat, class Triangle, in-vector InVec1, in-vector InVec2, out-vector OutVec> void hermitian_matrix_vector_product(InMat A, Triangle t, InVec1 x, InVec2 y, OutVec z); template<class ExecutionPolicy, in-matrix InMat, class Triangle, in-vector InVec1, in-vector InVec2, out-vector OutVec> void hermitian_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, InVec1 x, InVec2 y, OutVec z);
These functions perform an updating Hermitian matrix-vector product, taking into account the Triangle parameter that applies to the Hermitian matrix A ([linalg.general]).
Effects: Computes .
Remarks: z may alias y.

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

[Note 1: 
These functions correspond to the BLAS functions xTRMV and xTPMV[bib].
— end note]
The following elements apply to all functions in [linalg.algs.blas2.trmv].
Mandates:
  • If InMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true;
  • compatible-static-extents<decltype(A), decltype(y)>(0, 0) is true;
  • compatible-static-extents<decltype(A), decltype(x)>(0, 0) is true for those overloads that take an x parameter; and
  • compatible-static-extents<decltype(A), decltype(z)>(0, 0) is true for those overloads that take a z parameter.
Preconditions:
  • A.extent(0) equals A.extent(1),
  • A.extent(0) equals y.extent(0),
  • A.extent(0) equals x.extent(0) for those overloads that take an x parameter, and
  • A.extent(0) equals z.extent(0) for those overloads that take a z parameter.
template<in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec> void triangular_matrix_vector_product(InMat A, Triangle t, DiagonalStorage d, InVec x, OutVec y); template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec> void triangular_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InVec x, OutVec y);
These functions perform an overwriting triangular matrix-vector product, taking into account the Triangle and DiagonalStorage parameters that apply to the triangular matrix A ([linalg.general]).
Effects: Computes .
Complexity: .
template<in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec> void triangular_matrix_vector_product(InMat A, Triangle t, DiagonalStorage d, InOutVec y); template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec> void triangular_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InOutVec y);
These functions perform an in-place triangular matrix-vector product, taking into account the Triangle and DiagonalStorage parameters that apply to the triangular matrix A ([linalg.general]).
[Note 2: 
Performing this operation in place hinders parallelization.
However, other ExecutionPolicy specific optimizations, such as vectorization, are still possible.
— end note]
Effects: Computes a vector such that , and assigns each element of to the corresponding element of y.
Complexity: .
template<in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec1, in-vector InVec2, out-vector OutVec> void triangular_matrix_vector_product(InMat A, Triangle t, DiagonalStorage d, InVec1 x, InVec2 y, OutVec z); template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec1, in-vector InVec2, out-vector OutVec> void triangular_matrix_vector_product(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InVec1 x, InVec2 y, OutVec z);
These functions perform an updating triangular matrix-vector product, taking into account the Triangle and DiagonalStorage parameters that apply to the triangular matrix A ([linalg.general]).
Effects: Computes .
Complexity: .
Remarks: z may alias y.

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

[Note 1: 
These functions correspond to the BLAS functions xTRSV and xTPSV[bib].
— end note]
The following elements apply to all functions in [linalg.algs.blas2.trsv].
Mandates:
  • If InMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true;
  • compatible-static-extents<decltype(A), decltype(b)>(0, 0) is true; and
  • compatible-static-extents<decltype(A), decltype(x)>(0, 0) is true for those overloads that take an x parameter.
Preconditions:
  • A.extent(0) equals A.extent(1),
  • A.extent(0) equals b.extent(0), and
  • A.extent(0) equals x.extent(0) for those overloads that take an x parameter.
template<in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec, class BinaryDivideOp> void triangular_matrix_vector_solve(InMat A, Triangle t, DiagonalStorage d, InVec b, OutVec x, BinaryDivideOp divide); template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec, class BinaryDivideOp> void triangular_matrix_vector_solve(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InVec b, OutVec x, BinaryDivideOp divide);
These functions perform a triangular solve, taking into account the Triangle and DiagonalStorage parameters that apply to the triangular matrix A ([linalg.general]).
Effects: Computes a vector such that , and assigns each element of to the corresponding element of x.
If no such exists, then the elements of x are valid but unspecified.
Complexity: .
template<in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec> void triangular_matrix_vector_solve(InMat A, Triangle t, DiagonalStorage d, InVec b, OutVec x);
Effects: Equivalent to: triangular_matrix_vector_solve(A, t, d, b, x, divides<void>{});
template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, in-vector InVec, out-vector OutVec> void triangular_matrix_vector_solve(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InVec b, OutVec x);
Effects: Equivalent to: triangular_matrix_vector_solve(std::forward<ExecutionPolicy>(exec), A, t, d, b, x, divides<void>{});
template<in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec, class BinaryDivideOp> void triangular_matrix_vector_solve(InMat A, Triangle t, DiagonalStorage d, InOutVec b, BinaryDivideOp divide); template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec, class BinaryDivideOp> void triangular_matrix_vector_solve(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InOutVec b, BinaryDivideOp divide);
These functions perform an in-place triangular solve, taking into account the Triangle and DiagonalStorage parameters that apply to the triangular matrix A ([linalg.general]).
[Note 2: 
Performing triangular solve in place hinders parallelization.
However, other ExecutionPolicy specific optimizations, such as vectorization, are still possible.
— end note]
Effects: Computes a vector such that , and assigns each element of to the corresponding element of b.
If no such exists, then the elements of b are valid but unspecified.
Complexity: .
template<in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec> void triangular_matrix_vector_solve(InMat A, Triangle t, DiagonalStorage d, InOutVec b);
Effects: Equivalent to: triangular_matrix_vector_solve(A, t, d, b, divides<void>{});
template<class ExecutionPolicy, in-matrix InMat, class Triangle, class DiagonalStorage, inout-vector InOutVec> void triangular_matrix_vector_solve(ExecutionPolicy&& exec, InMat A, Triangle t, DiagonalStorage d, InOutVec b);
Effects: Equivalent to: triangular_matrix_vector_solve(std::forward<ExecutionPolicy>(exec), A, t, d, b, divides<void>{});

29.9.14.6 Rank-1 (outer product) update of a matrix [linalg.algs.blas2.rank1]

template<in-vector InVec1, in-vector InVec2, inout-matrix InOutMat> void matrix_rank_1_update(InVec1 x, InVec2 y, InOutMat A); template<class ExecutionPolicy, in-vector InVec1, in-vector InVec2, inout-matrix InOutMat> void matrix_rank_1_update(ExecutionPolicy&& exec, InVec1 x, InVec2 y, InOutMat A);
These functions perform a nonsymmetric nonconjugated rank-1 update.
[Note 1: 
These functions correspond to the BLAS functions xGER (for real element types) and xGERU (for complex element types)[bib].
— end note]
Mandates: possibly-multipliable<InOutMat, InVec2, InVec1>() is true.
Preconditions: multipliable(A, y, x) is true.
Effects: Computes a matrix such that , and assigns each element of to the corresponding element of A.
Complexity: .
template<in-vector InVec1, in-vector InVec2, inout-matrix InOutMat> void matrix_rank_1_update_c(InVec1 x, InVec2 y, InOutMat A); template<class ExecutionPolicy, in-vector InVec1, in-vector InVec2, inout-matrix InOutMat> void matrix_rank_1_update_c(ExecutionPolicy&& exec, InVec1 x, InVec2 y, InOutMat A);
These functions perform a nonsymmetric conjugated rank-1 update.
[Note 2: 
These functions correspond to the BLAS functions xGER (for real element types) and xGERC (for complex element types)[bib].
— end note]
Effects:
  • For the overloads without an ExecutionPolicy argument, equivalent to: matrix_rank_1_update(x, conjugated(y), A);
  • otherwise, equivalent to: matrix_rank_1_update(std::forward<ExecutionPolicy>(exec), x, conjugated(y), A);

29.9.14.7 Symmetric or Hermitian Rank-1 (outer product) update of a matrix [linalg.algs.blas2.symherrank1]

[Note 1: 
These functions correspond to the BLAS functions xSYR, xSPR, xHER, and xHPR[bib].
They have overloads taking a scaling factor alpha, because it would be impossible to express the update otherwise.
— end note]
The following elements apply to all functions in [linalg.algs.blas2.symherrank1].
Mandates:
  • If InOutMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true; and
  • compatible-static-extents<decltype(A), decltype(x)>(0, 0) is true.
Preconditions:
  • A.extent(0) equals A.extent(1), and
  • A.extent(0) equals x.extent(0).
Complexity: .
template<class Scalar, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_1_update(Scalar alpha, InVec x, InOutMat A, Triangle t); template<class ExecutionPolicy, class Scalar, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_1_update(ExecutionPolicy&& exec, Scalar alpha, InVec x, InOutMat A, Triangle t);
These functions perform a symmetric rank-1 update of the symmetric matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes a matrix such that , where the scalar α is alpha, and assigns each element of to the corresponding element of A.
template<in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_1_update(InVec x, InOutMat A, Triangle t); template<class ExecutionPolicy, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_1_update(ExecutionPolicy&& exec, InVec x, InOutMat A, Triangle t);
These functions perform a symmetric rank-1 update of the symmetric matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes a matrix such that and assigns each element of to the corresponding element of A.
template<class Scalar, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_1_update(Scalar alpha, InVec x, InOutMat A, Triangle t); template<class ExecutionPolicy, class Scalar, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_1_update(ExecutionPolicy&& exec, Scalar alpha, InVec x, InOutMat A, Triangle t);
These functions perform a Hermitian rank-1 update of the Hermitian matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes such that , where the scalar α is alpha, and assigns each element of to the corresponding element of A.
template<in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_1_update(InVec x, InOutMat A, Triangle t); template<class ExecutionPolicy, in-vector InVec, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_1_update(ExecutionPolicy&& exec, InVec x, InOutMat A, Triangle t);
These functions perform a Hermitian rank-1 update of the Hermitian matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes a matrix such that and assigns each element of to the corresponding element of A.

29.9.14.8 Symmetric and Hermitian rank-2 matrix updates [linalg.algs.blas2.rank2]

[Note 1: 
These functions correspond to the BLAS functions xSYR2,xSPR2, xHER2 and xHPR2[bib].
— end note]
The following elements apply to all functions in [linalg.algs.blas2.rank2].
Mandates:
  • If InOutMat has layout_blas_packed layout, then the layout's Triangle template argument has the same type as the function's Triangle template argument;
  • compatible-static-extents<decltype(A), decltype(A)>(0, 1) is true; and
  • possibly-multipliable<decltype(A), decltype(x), decltype(y)>() is true.
Preconditions:
  • A.extent(0) equals A.extent(1), and
  • multipliable(A, x, y) is true.
Complexity: .
template<in-vector InVec1, in-vector InVec2, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_2_update(InVec1 x, InVec2 y, InOutMat A, Triangle t); template<class ExecutionPolicy, in-vector InVec1, in-vector InVec2, possibly-packed-inout-matrix InOutMat, class Triangle> void symmetric_matrix_rank_2_update(ExecutionPolicy&& exec, InVec1 x, InVec2 y, InOutMat A, Triangle t);
These functions perform a symmetric rank-2 update of the symmetric matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes such that and assigns each element of to the corresponding element of A.
template<in-vector InVec1, in-vector InVec2, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_2_update(InVec1 x, InVec2 y, InOutMat A, Triangle t); template<class ExecutionPolicy, in-vector InVec1, in-vector InVec2, possibly-packed-inout-matrix InOutMat, class Triangle> void hermitian_matrix_rank_2_update(ExecutionPolicy&& exec, InVec1 x, InVec2 y, InOutMat A, Triangle t);
These functions perform a Hermitian rank-2 update of the Hermitian matrix A, taking into account the Triangle parameter that applies to A ([linalg.general]).
Effects: Computes such that and assigns each element of to the corresponding element of A.