Working with dense data in RandBLAS

Sketching dense matrices and vectors

RandBLAS has adaptions of GEMM, GEMV, and SYMM when one of their matrix operands is a sketching operator. These adaptations are provided through overloaded functions named sketch_general, sketch_vector, and sketch_symmetric.

Out of the functions presented here, only sketch_general has low-level implementations; sketch_vector and sketch_symmetric are basic wrappers around sketch_general, and are provided to make implementations less error-prone when porting code that currently uses BLAS or a BLAS-like interface.

Analogs to GEMM

\(\mathbf{B} = \alpha \cdot \operatorname{op}(\mathbf{S})\cdot \operatorname{op}(\mathbf{A}) + \beta \cdot \mathbf{B}\)

template<typename T, SketchingOperator SKOP>
inline void RandBLAS::sketch_general(blas::Layout layout, blas::Op opS, blas::Op opA, int64_t d, int64_t n, int64_t m, T alpha, SKOP &S, const T *A, int64_t lda, T beta, T *B, int64_t ldb)

Sketch from the left in a GEMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{op}(\mathbf{S})}_{d \times m} \cdot \underbrace{\operatorname{op}(\operatorname{mat}(A))}_{m \times n} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{d \times n}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars, \(\operatorname{op}(\mathbf{X})\) either returns a matrix \(\mathbf{X}\) or its transpose, and \(\mathbf{S}\) is a sketching operator.

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B).\)

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}.\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}^T.\)

opA - [in]

• If \(\texttt{opA}\) == NoTrans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A).\)

• If \(\texttt{opA}\) == Trans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A)^T.\)

d - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B)\)

• The number of rows in \(\operatorname{op}(\operatorname{mat}(S)).\)

n - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B)\)

• The number of columns in \(\operatorname{op}(\operatorname{mat}(A)).\)

m - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{op}(\mathbf{S}).\)

• The number of rows in \(\operatorname{op}(\operatorname{mat}(A)).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

\(\mathbf{B} = \alpha \cdot \operatorname{op}(\mathbf{A})\cdot \operatorname{op}(\mathbf{S}) + \beta \cdot \mathbf{B}\)

template<typename T, SketchingOperator SKOP>
inline void RandBLAS::sketch_general(blas::Layout layout, blas::Op opA, blas::Op opS, int64_t m, int64_t d, int64_t n, T alpha, const T *A, int64_t lda, SKOP &S, T beta, T *B, int64_t ldb)

Sketch from the right in a GEMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{op}(\operatorname{mat}(A))}_{m \times n} \cdot \underbrace{\operatorname{op}(\mathbf{S})}_{n \times d} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{m \times d}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars, \(\operatorname{op}(\mathbf{X})\) either returns a matrix \(\mathbf{X}\) or its transpose, and \(\mathbf{S}\) is a sketching operator.

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B).\)

opA - [in]

• If \(\texttt{opA}\) == NoTrans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A).\)

• If \(\texttt{opA}\) == Trans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A)^T.\)

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}.\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}^T.\)

m - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B).\)

• The number of rows in \(\operatorname{op}(\operatorname{mat}(A)).\)

d - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B).\)

• The number of columns in \(\operatorname{op}(\operatorname{mat}(S)).\)

n - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{op}(\operatorname{mat}(A)).\)

• The number of rows in \(\operatorname{op}(\mathbf{S}).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

S - [in]

• A DenseSkOp or SparseSkOp object.

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

Variants using \(\operatorname{op}(\operatorname{submat}(\mathbf{S}))\)

template<typename T, SketchingOperator SKOP>
inline void RandBLAS::sketch_general(blas::Layout layout, blas::Op opS, blas::Op opA, int64_t d, int64_t n, int64_t m, T alpha, SKOP &S, int64_t ro_s, int64_t co_s, const T *A, int64_t lda, T beta, T *B, int64_t ldb)

Sketch from the left in a GEMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{op}(\operatorname{submat}(\mathbf{S}))}_{d \times m} \cdot \underbrace{\operatorname{op}(\operatorname{mat}(A))}_{m \times n} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{d \times n}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars, \(\operatorname{op}(\mathbf{X})\) either returns a matrix \(\mathbf{X}\) or its transpose, and \(\mathbf{S}\) is a sketching operator.

FAQ

What are \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B)\) ?

Their shapes are defined implicitly by \((d, m, n, \texttt{opA}).\) Their precise contents are determined by \((A, \texttt{lda}),\) \((B, \texttt{ldb}),\) and “layout”, following the same convention as GEMM from BLAS.

If layout == ColMajor, then

\[\operatorname{mat}(A)_{ij} = A[i + j \cdot \texttt{lda}].\]

In this case, \(\texttt{lda}\) must be \(\geq\) the length of a column in \(\operatorname{mat}(A).\)

If layout == RowMajor, then

\[\operatorname{mat}(A)_{ij} = A[i \cdot \texttt{lda} + j].\]

In this case, \(\texttt{lda}\) must be \(\geq\) the length of a row in \(\operatorname{mat}(A).\)

What is \(\operatorname{submat}(\mathbf{S})\) ?

Its shape is defined implicitly by \((\texttt{opS}, d, m).\)

If \({\operatorname{submat}(\mathbf{S})}\) is of shape \(r \times c,\) then it is the \(r \times c\) submatrix of \({\mathbf{S}}\) whose upper-left corner appears at index \((\texttt{ro_s}, \texttt{co_s})\) of \({\mathbf{S}}.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B).\)

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S}).\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S})^T.\)

opA - [in]

• If \(\texttt{opA}\) == NoTrans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A).\)

• If \(\texttt{opA}\) == Trans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A)^T.\)

d - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B)\)

• The number of rows in \(\operatorname{op}(\operatorname{submat}(\mathbf{S})).\)

n - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B)\)

• The number of columns in \(\operatorname{op}(\operatorname{mat}(A)).\)

m - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{op}(\operatorname{submat}(\mathbf{S}))\)

• The number of rows in \(\operatorname{op}(\operatorname{mat}(A)).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

ro_s - [in]

• A nonnegative integer.

• The rows of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of rows of \(S.\)

• The rows of \(\operatorname{submat}(\mathbf{S})\) start at \(S[\texttt{ro_s}, :].\)

co_s - [in]

• A nonnnegative integer.

• The columns of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of columns of \(S.\)

• The columns of \(\operatorname{submat}(\mathbf{S})\) start at \(S[:,\texttt{co_s}].\)

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

template<typename T, SketchingOperator SKOP>
inline void RandBLAS::sketch_general(blas::Layout layout, blas::Op opA, blas::Op opS, int64_t m, int64_t d, int64_t n, T alpha, const T *A, int64_t lda, SKOP &S, int64_t ro_s, int64_t co_s, T beta, T *B, int64_t ldb)

Sketch from the right in a GEMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{op}(\operatorname{mat}(A))}_{m \times n} \cdot \underbrace{\operatorname{op}(\operatorname{submat}(\mathbf{S}))}_{n \times d} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{m \times d}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars, \(\operatorname{op}(\mathbf{X})\) either returns a matrix \(\mathbf{X}\) or its transpose, and \(\mathbf{S}\) is a sketching operator.

FAQ

What are \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B)\) ?

Their shapes are defined implicitly by \((m, d, n, \texttt{opA}).\) Their precise contents are determined by \((A, \texttt{lda}),\) \((B, \texttt{ldb}),\) and “layout”, following the same convention as the Level 3 BLAS function “GEMM.”

What is \(\operatorname{submat}(\mathbf{S})\) ?

Its shape is defined implicitly by \((\texttt{opS}, n, d).\) If \({\operatorname{submat}(\mathbf{S})}\) is of shape \(r \times c,\) then it is the \(r \times c\) submatrix of \({\mathbf{S}}\) whose upper-left corner appears at index \((\texttt{ro_s}, \texttt{co_s})\) of \({\mathbf{S}}.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(A)\) and \(\operatorname{mat}(B).\)

opA - [in]

• If \(\texttt{opA}\) == NoTrans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A).\)

• If \(\texttt{opA}\) == Trans, then \(\operatorname{op}(\operatorname{mat}(A)) = \operatorname{mat}(A)^T.\)

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S}).\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S})^T.\)

m - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B).\)

• The number of rows in \(\operatorname{op}(\operatorname{mat}(A)).\)

d - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B)\)

• The number of columns in \(\operatorname{op}(\operatorname{submat}(\mathbf{S})).\)

n - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{op}(\operatorname{mat}(A)).\)

• The number of rows in \(\operatorname{op}(\operatorname{submat}(\mathbf{S})).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

• Defines \(\operatorname{submat}(\mathbf{S}).\)

ro_s - [in]

• A nonnegative integer.

• The rows of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of rows of \(S.\)

• The rows of \(\operatorname{submat}(\mathbf{S})\) start at \(S[\texttt{ro_s}, :].\)

co_s - [in]

• A nonnegative integer.

• The columns of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of columns of \(S.\)

• The columns \(\operatorname{submat}(\mathbf{S})\) start at \(S[:,\texttt{co_s}].\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

Analogs to SYMM

\(\mathbf{B} = \alpha \cdot \mathbf{S} \cdot \mathbf{A} + \beta \cdot \mathbf{B}\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_symmetric(blas::Layout layout, T alpha, SKOP &S, const T *A, int64_t lda, T beta, T *B, int64_t ldb, T sym_check_tol = 0)

Check that \(\operatorname{mat}(A)\) is symmetric up to tolerance \(\texttt{sym_check_tol}\), then sketch from the left in a SYMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \mathbf{S} \cdot \underbrace{\operatorname{mat}(A)}_{n \times n} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{d \times n}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is a \(d \times n\) sketching operator.

FAQ

What’s \(\operatorname{mat}(A)?\)

It’s a symmetric matrix of order \(n\). Its precise contents depend on \((A, \texttt{lda})\), according to

\[\operatorname{mat}(A)_{ij} = A[i + j \cdot \texttt{lda}] = A[i \cdot \texttt{lda} + j].\]

Note that the the “layout” parameter passed to this function is not used here. That’s because this function requires \(\operatorname{mat}(A)\) to be stored in the format of a general matrix (with both upper and lower triangles).

This function’s default behavior is to check that \(\operatorname{mat}(A)\) is symmetric before attempting sketching. That check can be skipped (at your own peril!) by calling this function with sym_check_tol < 0.

What’s \(\operatorname{mat}(B)?\)

It’s a \(d \times n\) matrix. Its precise contents depend on \((B,\texttt{ldb})\) and “layout.”

If layout == ColMajor, then

\[\operatorname{mat}(B)_{ij} = B[i + j \cdot \texttt{ldb}].\]

In this case, \(\texttt{ldb}\) must be \(\geq d.\)

If layout == RowMajor, then

\[\operatorname{mat}(B)_{ij} = B[i \cdot \texttt{ldb} + j].\]

In this case, \(\texttt{ldb}\) must be \(\geq n.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(B).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

\(\mathbf{B} = \alpha \cdot \mathbf{A} \cdot \mathbf{S} + \beta \cdot \mathbf{B}\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_symmetric(blas::Layout layout, T alpha, const T *A, int64_t lda, SKOP &S, T beta, T *B, int64_t ldb, T sym_check_tol = 0)

Check that \(\operatorname{mat}(A)\) is symmetric up to tolerance \(\texttt{sym_check_tol}\), then sketch from the right in a SYMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{mat}(A)}_{n \times n} \cdot \mathbf{S} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{n \times d}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is an \(n \times d\) sketching operator.

FAQ

What’s \(\operatorname{mat}(A)?\)

It’s a symmetric matrix of order \(n\), where \(n = \texttt{S.dist.n_cols}\). Its precise contents depend on \((A, \texttt{lda})\), according to

\[\operatorname{mat}(A)_{ij} = A[i + j \cdot \texttt{lda}] = A[i \cdot \texttt{lda} + j].\]

Note that the the “layout” parameter passed to this function is not used here. That’s because this function requires \(\operatorname{mat}(A)\) to be stored in the format of a general matrix (with both upper and lower triangles).

This function’s default behavior is to check that \(\operatorname{mat}(A)\) is symmetric before attempting sketching. That check can be skipped (at your own peril!) by calling this function with sym_check_tol < 0.

What’s \(\operatorname{mat}(B)?\)

It’s an \(n \times d\) matrix, where \(n = \texttt{S.dist.n_cols}\) and \(d = \texttt{S.dist.n_rows}\). Its precise contents depend on \((B,\texttt{ldb})\) and “layout.”

If layout == ColMajor, then

\[\operatorname{mat}(B)_{ij} = B[i + j \cdot \texttt{ldb}].\]

In this case, \(\texttt{ldb}\) must be \(\geq n.\)

If layout == RowMajor, then

\[\operatorname{mat}(B)_{ij} = B[i \cdot \texttt{ldb} + j].\]

In this case, \(\texttt{ldb}\) must be \(\geq d.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(B).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

S - [in]

• A DenseSkOp or SparseSkOp object.

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

Variants using \(\operatorname{submat}(\mathbf{S})\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_symmetric(blas::Layout layout, int64_t d, int64_t n, T alpha, SKOP &S, int64_t ro_s, int64_t co_s, const T *A, int64_t lda, T beta, T *B, int64_t ldb, T sym_check_tol = 0)

Check that \(\operatorname{mat}(A)\) is symmetric up to tolerance \(\texttt{sym_check_tol}\), then sketch from the left in a SYMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{submat}(\mathbf{S})}_{d \times n} \cdot \underbrace{\operatorname{mat}(A)}_{n \times n} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{d \times n}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is a sketching operator.

FAQ

What’s \(\operatorname{mat}(A)?\)

It’s a symmetric matrix of order \(n\). Its precise contents depend on \((A, \texttt{lda})\), according to

\[\operatorname{mat}(A)_{ij} = A[i + j \cdot \texttt{lda}] = A[i \cdot \texttt{lda} + j].\]

Note that the the “layout” parameter passed to this function is not used here. That’s because this function requires \(\operatorname{mat}(A)\) to be stored in the format of a general matrix (with both upper and lower triangles).

This function’s default behavior is to check that \(\operatorname{mat}(A)\) is symmetric before attempting sketching. That check can be skipped (at your own peril!) by calling this function with sym_check_tol < 0.

What’s \(\operatorname{mat}(B)?\)

It’s a \(d \times n\) matrix. Its precise contents depend on \((B,\texttt{ldb})\) and “layout.”

If layout == ColMajor, then

\[\operatorname{mat}(B)_{ij} = B[i + j \cdot \texttt{ldb}].\]

In this case, \(\texttt{ldb}\) must be \(\geq d.\)

If layout == RowMajor, then

\[\operatorname{mat}(B)_{ij} = B[i \cdot \texttt{ldb} + j].\]

In this case, \(\texttt{ldb}\) must be \(\geq n.\)

What is \(\operatorname{submat}(\mathbf{S})\) ?

It’s the \(d \times n\) submatrix of \({\mathbf{S}}\) whose upper-left corner appears at index \((\texttt{ro_s}, \texttt{co_s})\) of \({\mathbf{S}}.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(B).\)

d - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B)\) and \(\operatorname{submat}(\mathbf{S}).\)

n - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B).\)

• The number of rows and columns in \(\operatorname{mat}(A).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

ro_s - [in]

• A nonnegative integer.

• The rows of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of rows of \(S.\)

• The rows of \(\operatorname{submat}(\mathbf{S})\) start at \(S[\texttt{ro_s}, :].\)

co_s - [in]

• A nonnnegative integer.

• The columns of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of columns of \(S.\)

• The columns of \(\operatorname{submat}(\mathbf{S})\) start at \(S[:,\texttt{co_s}].\)

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_symmetric(blas::Layout layout, int64_t n, int64_t d, T alpha, const T *A, int64_t lda, SKOP &S, int64_t ro_s, int64_t co_s, T beta, T *B, int64_t ldb, T sym_check_tol = 0)

Check that \(\operatorname{mat}(A)\) is symmetric up to tolerance \(\texttt{sym_check_tol}\), then sketch from the right in a SYMM-like operation

\[\operatorname{mat}(B) = \alpha \cdot \underbrace{\operatorname{mat}(A)}_{n \times n} \cdot \underbrace{\operatorname{submat}(\mathbf{S})}_{n \times d} + \beta \cdot \underbrace{\operatorname{mat}(B)}_{n \times d}, \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is a sketching operator.

FAQ

What’s \(\operatorname{mat}(A)?\)

It’s a symmetric matrix of order \(n\). Its precise contents depend on \((A, \texttt{lda})\), according to

\[\operatorname{mat}(A)_{ij} = A[i + j \cdot \texttt{lda}] = A[i \cdot \texttt{lda} + j].\]

Note that the the “layout” parameter passed to this function is not used here. That’s because this function requires \(\operatorname{mat}(A)\) to be stored in the format of a general matrix (with both upper and lower triangles).

This function’s default behavior is to check that \(\operatorname{mat}(A)\) is symmetric before attempting sketching. That check can be skipped (at your own peril!) by calling this function with sym_check_tol < 0.

What’s \(\operatorname{mat}(B)?\)

It’s an \(n \times d\) matrix. Its precise contents depend on \((B,\texttt{ldb})\) and “layout.”

If layout == ColMajor, then

\[\operatorname{mat}(B)_{ij} = B[i + j \cdot \texttt{ldb}].\]

In this case, \(\texttt{ldb}\) must be \(\geq n.\)

If layout == RowMajor, then

\[\operatorname{mat}(B)_{ij} = B[i \cdot \texttt{ldb} + j].\]

In this case, \(\texttt{ldb}\) must be \(\geq d.\)

What is \(\operatorname{submat}(\mathbf{S})\) ?

It’s the \(n \times d\) submatrix of \({\mathbf{S}}\) whose upper-left corner appears at index \((\texttt{ro_s}, \texttt{co_s})\) of \({\mathbf{S}}.\)

Full parameter descriptions

layout - [in]

• Either Layout::ColMajor or Layout::RowMajor

• Matrix storage for \(\operatorname{mat}(B).\)

n - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{mat}(B).\)

• The number of rows and columns in \(\operatorname{mat}(A).\)

d - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{mat}(B)\) and \(\operatorname{submat}(\mathbf{S}).\)

alpha - [in]

• A real scalar.

• If zero, then \(A\) is not accessed.

A - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(A).\)

lda - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(A)\) when reading from \(A.\)

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

ro_s - [in]

• A nonnegative integer.

• The rows of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of rows of \(S.\)

• The rows of \(\operatorname{submat}(\mathbf{S})\) start at \(S[\texttt{ro_s}, :].\)

co_s - [in]

• A nonnnegative integer.

• The columns of \(\operatorname{submat}(\mathbf{S})\) are a contiguous subset of columns of \(S.\)

• The columns of \(\operatorname{submat}(\mathbf{S})\) start at \(S[:,\texttt{co_s}].\)

beta - [in]

• A real scalar.

• If zero, then \(B\) need not be set on input.

B - [in,out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(B)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(B)\) on the LEFT-hand side of \((\star).\)

ldb - [in]

• A nonnegative integer.

• Leading dimension of \(\operatorname{mat}(B)\) when reading from \(B.\)

Analogs to GEMV

\(\mathbf{y} = \alpha \cdot \operatorname{op}(\mathbf{S}) \cdot \mathbf{x} + \beta \cdot \mathbf{y}\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_vector(blas::Op opS, T alpha, SKOP &S, const T *x, int64_t incx, T beta, T *y, int64_t incy)

Perform a GEMV-like operation:

\[\operatorname{mat}(y) = \alpha \cdot \operatorname{op}(\mathbf{S}) \cdot \operatorname{mat}(x) + \beta \cdot \operatorname{mat}(y), \tag{$\star$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is a sketching operator.

FAQ

What are \(\operatorname{mat}(x)\) and \(\operatorname{mat}(y)\) ?

They are vectors of shapes \((\operatorname{mat}(x), L_x \times 1)\) and \((\operatorname{mat}(y), L_y \times 1),\) where \((L_x, L_y)\) are lengths so that \(\texttt{opS}(\mathbf{S}) \operatorname{mat}(x)\) is well-defined and the same shape as \(\operatorname{mat}(y).\) Their precise contents are determined in a way that is identical to GEMV from BLAS.

Why no “layout” argument?

GEMV in CBLAS accepts a parameter that specifies row-major or column-major layout of the matrix operand. Since our matrix is a sketching operator, and since RandBLAS has no notion of the layout of a sketching operator, we do not have a layout parameter.

Full parameter descriptions

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}.\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\mathbf{S}) = \mathbf{S}^T.\)

alpha - [in]

• A real scalar.

• If zero, then \(x\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

x - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(x).\)

incx - [in]

• A positive integer.

• Stride between elements of x.

beta - [in]

• A real scalar.

• If zero, then \(y\) need not be set on input.

y - [in, out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(y)\) on the RIGHT-hand side of \((\star).\)

• On exit, defines \(\operatorname{mat}(y)\) on the LEFT-hand side of the same.

incy - [in]

• A positive integer.

• Stride between elements of y.

Variants using \(\operatorname{op}(\operatorname{submat}(\mathbf{S}))\)

template<SketchingOperator SKOP, typename T = SKOP::scalar_t>
inline void RandBLAS::sketch_vector(blas::Op opS, int64_t d, int64_t m, T alpha, SKOP &S, int64_t ro_s, int64_t co_s, const T *x, int64_t incx, T beta, T *y, int64_t incy)

Perform a GEMV-like operation. If \({\texttt{opS}} = \texttt{NoTrans},\) then we perform

\[\operatorname{mat}(y) = \alpha \cdot \underbrace{\operatorname{submat}(\mathbf{S})}_{d \times m} \cdot \underbrace{\operatorname{mat}(x)}_{m \times 1} + \beta \cdot \underbrace{\operatorname{mat}(y)}_{d \times 1}, \tag{$\star$}\]

otherwise, we perform

\[\operatorname{mat}(y) = \alpha \cdot \underbrace{\operatorname{submat}(\mathbf{S})^T}_{m \times d} \cdot \underbrace{\operatorname{mat}(x)}_{d \times 1} + \beta \cdot \underbrace{\operatorname{mat}(y)}_{m \times 1}, \tag{$\diamond$}\]

where \(\alpha\) and \(\beta\) are real scalars and \(\mathbf{S}\) is a sketching operator.

FAQ

What are \(\operatorname{mat}(x)\) and \(\operatorname{mat}(y)\) ?

They are vectors of shapes \((\operatorname{mat}(x), L_x \times 1)\) and \((\operatorname{mat}(y), L_y \times 1),\) where \((L_x, L_y)\) are lengths so that \(opS(\operatorname{submat}(\mathbf{S})) \operatorname{mat}(x)\) is well-defined and the same shape as \(\operatorname{mat}(y).\) Their precise contents are determined in a way that is identical to GEMV from BLAS.

Why no “layout” argument?

GEMV in CBLAS accepts a parameter that specifies row-major or column-major layout of the matrix operand. Since our matrix is a sketching operator, and since RandBLAS has no notion of the layout of a sketching operator, we do not have a layout parameter.

Full parameter descriptions

opS - [in]

• Either Op::Trans or Op::NoTrans.

• If \(\texttt{opS}\) = NoTrans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S}).\)

• If \(\texttt{opS}\) = Trans, then \(\operatorname{op}(\operatorname{submat}(\mathbf{S})) = \operatorname{submat}(\mathbf{S})^T.\)

d - [in]

• A nonnegative integer.

• The number of rows in \(\operatorname{submat}(\mathbf{S}).\)

m - [in]

• A nonnegative integer.

• The number of columns in \(\operatorname{submat}(\mathbf{S}).\)

alpha - [in]

• A real scalar.

• If zero, then \(x\) is not accessed.

S - [in]

• A DenseSkOp or SparseSkOp object.

• Defines \(\operatorname{submat}(\mathbf{S}).\)

ro_s - [in]

• A nonnegative integer.

• \(\operatorname{submat}(\mathbf{S})\) is a contiguous submatrix of \(S[\texttt{ro_s}:(\texttt{ro_s} + d), :].\)

co_s - [in]

• A nonnegative integer.

• \(\operatorname{submat}(\mathbf{S})\) is a contiguous submatrix of \(S[:,\texttt{co_s}:(\texttt{co_s} + m)].\)

x - [in]

• Pointer to a 1D array of real scalars.

• Defines \(\operatorname{mat}(x).\)

incx - [in]

• A positive integer.

• Stride between elements of x.

beta - [in]

• A real scalar.

• If zero, then \(y\) need not be set on input.

y - [in, out]

• Pointer to 1D array of real scalars.

• On entry, defines \(\operatorname{mat}(y)\) on the RIGHT-hand side of \((\star)\) (if \(\texttt{opS} = \texttt{NoTrans}\)) or \((\diamond)\) (if \(\texttt{opS} = \texttt{Trans}\))

• On exit, defines \(\operatorname{mat}(y)\) on the LEFT-hand side of the same.

incy - [in]

• A positive integer.

• Stride between elements of y.

Matrix format utility functions

template<typename T>
void RandBLAS::symmetrize(blas::Layout layout, blas::Uplo uplo, int64_t n, T *A, int64_t lda)

Use this function to convert a matrix that BLAS can interpet as symmetric into a matrix that’s explicitly symmetric.

Formally, \(A\) points to the start of a buffer for an \(n \times n\) matrix \(\operatorname{mat}(A)\) stored in \(\texttt{layout}\) order with leading dimension \(\texttt{lda}.\) This function copies the strict part of the \(\texttt{uplo}\) triangle of \(\operatorname{mat}(A)\) into the strict part of the opposing triangle.

template<typename T>
void RandBLAS::transpose_square(T *A, int64_t n, int64_t lda)

In-place transpose of square matrix of order \(n\), with leading dimension \(\texttt{lda}.\)

It turns out that there’s no implementation difference between row-major or column-major data, so we don’t accept a layout parameter.

template<typename T>
void RandBLAS::overwrite_triangle(blas::Layout layout, blas::Uplo to_overwrite, int64_t n, int64_t k, T *A, int64_t lda)

Use this function to convert a matrix which BLAS can interpret as triangular into a matrix that’s explicitly triangular.

Formally, \(A\) points to the start of a buffer for an \(n \times n\) matrix \(\operatorname{mat}(A)\) stored in \(\texttt{layout}\) order with leading dimension \(\texttt{lda},\) and \(\texttt{k}\) is a nonnegative integer.

This function overwrites \(A\) so that …

• If \(\texttt{to_overwrite} = \texttt{Uplo::Lower},\) then elements of \(\operatorname{mat}(A)\) on or below its \(\texttt{k}^{\text{th}}\) subdiagonal are overwritten with zero.

• If \(\texttt{to_overwrite} = \texttt{Uplo::Upper},\) then elements of \(\operatorname{mat}(A)\) on or above its \(\texttt{k}^{\text{th}}\) superdiagonal are overwritten with zero.

This function raises an error if \(\texttt{k}\) is negative or if \(\texttt{to_overwrite}\) is neither Upper nor Lower.