Skip to content

Adopt one-triangle symmetric sketching (BallisticLA/RandBLAS#163) in ExplicitSymLinOp #167

Description

@mmelnich

Context

BallisticLA/RandBLAS#163 adds SYMM-shaped kernels to RandBLAS so that symmetric matrices can be sketched from one stored triangle. After that PR, sketch_symmetric dispatches to blas::symm for a DenseSkOp and to a one-triangle COO scatter kernel for a SparseSkOp (Case B in the PR's table), and the new spsymm covers sparse symmetric matrices. The PR also changes the sketch_symmetric signature: the sym_check_tol trailing argument is replaced by blas::Uplo uplo, which names the stored triangle.

RandLAPACK currently works around the missing functionality. ExplicitSymLinOp's sparse-SkOp apply path (linops/rl_sym_linops.hh, on the funNystrom++ branches) calls RandBLAS::sparse_data::right_spmm, which reads A as a general dense matrix. That forces BOTH triangles of A to be populated and adds a symmetrize-before-construct precondition for matrices that generators fill upper-only.

What needs to change once the RandBLAS side merges

  1. Bump the RandBLAS submodule pin past the merge commit.
  2. In ExplicitSymLinOp:
    • thread blas::Uplo uplo through the class and its sketch_symmetric-adjacent call sites (required by the signature change);
    • switch the sparse-SkOp apply path from right_spmm to RandBLAS::sketch_symmetric, which reads only the named triangle.
  3. Remove the both-triangles precondition and the callers' symmetrization steps that exist only to satisfy it.
  4. Audit any other sketch_symmetric consumers for the signature change.

Why

  • One-triangle storage end to end halves the memory footprint of a large explicit symmetric matrix. This is the funNystrom++ / Nystrom EVD use case; some target datasets (for example, large Gram or NTK matrices) are already distributed as a single triangle, so the fill step disappears entirely.
  • The symmetrize precondition and its bug surface go away.
  • Each sketch apply reads half of A.

Before switching the default

The Case B kernel is a hand-rolled per-nonzero scatter, while right_spmm on a fully stored A can route through MKL. Worth a quick benchmark on a funNystrom++-shaped problem (the spsymm_performance.cc example added in the RandBLAS PR covers the related comparisons) to confirm wall-clock parity. The memory argument stands regardless of the outcome.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions