Naming conventions for basic sketching

[rileyjmurray]

RandBLAS's support for basic sketching is taking shape. We have code and tests for any combination of sketching from the left or right and using a dense or sparse sketching operator. That is, we have code to compute

• $B = \alpha \cdot \mathrm{op}(S) \cdot \mathrm{op}(A) + \beta \cdot B$
• $B = \alpha \cdot \mathrm{op}(A)\cdot \mathrm{op}(S) + \beta\cdot B$

where $S$ is dense or sparse and $A$ is a general dense matrix.

This "GitHub Discussions" thread documents proposals for the naming of these functions (and similar functions) in RandBLAS.

Requirements

• We want functions that abstract away the type of the sketching operator (dense or sparse).
• We also want functions that have the sketching operator type (dense or sparse) in their names.
• We need separate functions for sketching from the left and right.
• We need separate functions for sketching structured matrices, such as Hermitian or symmetric matrices. See symm and hemm.

Where the discussion stands

The latest update to RandBLAS/main uses Option 2 below. RandBLAS/main also has older code that follows Option 1. We'll make these things consistent once we come to a consensus here.

I'm currently leaning towards Option 3 (not 3A). There's less ambiguity in how one might pronounce the constituent abbreviations compared to Option 3A. It has the ramm prefix to mimic gemm. The natural suffixes gefr, syfr, hefl, etc.. are readable insofar as the letter "f" signifies "from". The fully qualified names that include sparse or level3 should see limited use. As a result, we wouldn't want to abbreviate the sketching operator type in the manner suggested by Option 3B.

Things to keep in mind

• Naming conventions in the C++ community.
• The ability to easily overload functions in C++ and Fortran.
• The ability to overload functions in C (C11 and higher) via macros and _Generic.
• The extent to which we use namespaces.

We might converge on a naming convention for basic sketching, and yet still need to revisit this when we get to fancier things such as multi-sketching.

[rileyjmurray]

Option 1.

This isn't worth considering. I'm just keeping this up to document the discussion process.

• lskge, rskge
• lskhe, rskhe
• lsksy, lsksy.

The first character (l or r) signifies the side from which the sketching operator is applied. The next two characters, sk, abbreviate "sketch." The final two characters signify the type of the matrix to be sketched. These function names read like "left-sketch a general matrix" or "right-sketch a Hermitian matrix".

The type of the sketching operator could be incorporated into the function name with a single signifying character, such as 3 for operators that take BLAS 3 effort to apply and S for sparse operators. A function like lskges would read as "left-sketch a general matrix with a sparse sketching operator."

[rileyjmurray]

Comment: It's unusual to include ge, he, sy to indicate a general matrix in the middle of a function name. BLAS only puts this kind of signifier at the beginning of a function name.

The naive response to this observation is to rearrange lskge to something like gelsk. This isn't great because it's very close to the name of the LAPACK function gels.

[rileyjmurray]

sk suggests that the function computes a sketch. That's not strictly true since these functions can lift to higher dimensions as well. For example, you could compute $S^T B$ where $S$ is a wide sketching operator.

Alternatives like ra (random) or so (sketching operator) aren't great because they can't be read as verbs. Using these instead of sk would be like dropping the mm in gemm.

[rileyjmurray]

Option 2.

• ramm_general_left, ramm_general_right.
• ramm_hermitian_left, ramm_hermitian_right.
• ramm_symmetric_left, ramm_symmetric_right.

ramm is supposed to be evocative of gemm. Functions that specify the type of the sketching operator would probably need to look like ramm_general_right_sparse and ramm_general_right_dense.

[rileyjmurray]

Option 2A.

Being extra verbose:

ramm_[data matrix type]_from_[side]_by_[sketching operator type]

For example,

• ramm_general_from_left_by_sparse
• ramm_hermitian_from_right_by_level3
• ramm_general_from_right_by_any

[rileyjmurray]

Option 3.

• ramm_gefl / ramm_gefr
• ramm_hefl / ramm_hefr
• ramm_syfl / ramm_syfr

The f in these names abbreviates "from." The last character is l or r depending on if we're applied to a matrix from the left or right.

A function like ramm_gefl reads as "randomized matrix multiplication, hit a general data matrix from the left."

[rileyjmurray]

Option 3A.

I think that using f as an abbreviation of "from" is important here. If we dropped the requirement of having "from" appear in the function name, then we could do a two-character abbreviation of "left" and "right" to get an abbreviated form of Option 2:

• ramm_gele / ramm_geri
• ramm_hele / ramm_heri
• ramm_syle / ramm_syri

It's worth thinking about how we'd incorporate the type of the sketching operator into the function name.

• ramm_gele --> ramm_gele_any, ramm_gele_sparse, ramm_gele_level3
• ramm_geri --> ramm_geri_any, ramm_geri_sparse, ramm_geri_level3

This specification adds an _any suffix that could be dropped.

[rileyjmurray]

Option 3B

• ramm_gele --> ramm_gelean, ramm_gelesp, ramm_gelel3
• ramm_geri --> ramm_gerian, ramm_gerisp, ramm_geril3

This adds an an suffix that could be dropped.

It's hard to parse six-character sequences like gelel3 and geril3. Much easier to parse gele separately and l3 or level3

[rileyjmurray]

Option 3C.

Observation: we don't necessarily need ge, sy, he, tr, we could use g, s, h, t. If we shortened things this way then le and ri could be l and r.

We'd get things like

• ramm_gls, ramm_grs, ramm_gl3, ramm_gr3
• ramm_hls, ramm_hrs, ramm_hl3, ramm_hr3
• ramm_sls, ramm_srs, ramm_sl3, ramm_sr3

^ Those aren't pronounceable.

[rileyjmurray]

This comment is a short reference. Refer to later comments for details and thought processes.

Notes that apply to all options

• The acronym ramm stands for randomized matrix multiply
• The generic function that dispatches type-specific implementations could have no special suffix, or it could have a suffix _any.

Summary of options

Option 1 isn't worth considering.

Option 2

• ramm_general_left, ramm_general_right.
• ramm_hermitian_left, ramm_hermitian_right.
• ramm_symmetric_left, ramm_symmetric_right.
• Fully qualified examples
  • ramm_general_left_sparse
  • ramm_symmetric_right_level3

Option 2A

• ramm_general_from_left, ramm_general_from_right.
• ramm_hermitian_from_left, ramm_hermitian_from_right.
• ramm_symmetric_from_left, ramm_symmetric_from_right
• Fully-qualified examples
  • ramm_general_from_right_by_sparse
  • ramm_symmetric_from_left_by_level3

Option 3

• ramm_gefl / ramm_gefr
• ramm_hefl / ramm_hefr
• ramm_syfl / ramm_syfr
• Fully-qualified examples
  • ramm_gefr_sparse
  • ramm_syfl_level3

Option 3A

• ramm_gele / ramm_geri
• ramm_hele / ramm_heri
• ramm_syle / ramm_syri
• Fully-qualified examples
  • ramm_geri_sparse
  • ramm_syle_level3

There's also Option 3B and Option 3C. I don't think those are worth considering.

[TeachRaccooon]

Prompt

RandBLAS's support for basic sketching is taking shape. We have code and tests for any combination of sketching from the left or right and using a dense or sparse sketching operator. That is, we have code to compute

• B=α⋅op(S)⋅op(A)+β⋅B
• B=α⋅op(A)⋅op(S)+β⋅B

where S is dense or sparse and A is a general dense matrix.

This "GitHub Discussions" thread documents proposals for the naming of these functions (and similar functions) in RandBLAS.

Requirements

• We want functions that abstract away the type of the sketching operator (dense or sparse).
• We also want functions that have the sketching operator type (dense or sparse) in their names.
• We need separate functions for sketching from the left and right.
• We need separate functions for sketching structured matrices, such as Hermitian or symmetric matrices. See symm and hemm.

Things to keep in mind

• Naming conventions in the C++ community.
• The ability to easily overload functions in C++ and Fortran.
• The ability to overload functions in C (C11 and higher) via macros and _Generic.
• The extent to which we use namespaces.

We might converge on a naming convention for basic sketching, and yet still need to revisit this when we get to fancier things such as multi-sketching.

Options

Option 1 isn't worth considering.

Option 2

• ramm_general_left, ramm_general_right.

• ramm_hermitian_left, ramm_hermitian_right.

• ramm_symmetric_left, ramm_symmetric_right.

• Fully qualified examples

  • ramm_general_left_sparse
  • ramm_symmetric_right_level3

Option 2A

• ramm_general_from_left, ramm_general_from_right.

• ramm_hermitian_from_left, ramm_hermitian_from_right.

• ramm_symmetric_from_left, ramm_symmetric_from_right

• Fully-qualified examples

  • ramm_general_from_right_by_sparse
  • ramm_symmetric_from_left_by_level3

Option 3

• ramm_gefl / ramm_gefr

• ramm_hefl / ramm_hefr

• ramm_syfl / ramm_syfr

• Fully-qualified examples

  • ramm_gefr_sparse
  • ramm_syfl_level3

Option 3A

• ramm_gele / ramm_geri

• ramm_hele / ramm_heri

• ramm_syle / ramm_syri

• Fully-qualified examples

  • ramm_geri_sparse
  • ramm_syle_level3

There's also Option 3B and Option 3C. I don't think those are worth considering.

Feedback

I am in favor of option 3.
While it is a bit weird to include "from" into the name, without it, names do not sound well.

[rileyjmurray]

The table of naming conventions for the C++ linear algebra standard is here: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p1673r11.html#overview-of-contents (at the end of section 4).