search

pghysels / STRUMPACK

Structured Matrix Package (LBNL)
http://portal.nersc.gov/project/sparse/strumpack/
Other
167 stars 41 forks source link

[Feature Request] StructuredMatrix multiplication #67

Closed AlexGKim closed 2 years ago

AlexGKim commented 2 years ago

In my application, I take the product of two matrices with common hierarchical structure. In a conversation with @xiaoyeli , it was suggested that the product of two StructuredMatrices (or of common subclasses) could be very efficient. If this is the case, I request a StructuredMatrix::mult(StructuredMatrix).

xiaoyeli commented 2 years ago

I think right now we have efficient A*B, where A is a structured matrix, and B is a dense matrix. Do you really need both A and B are structured matrices? That will need new development.

AlexGKim commented 2 years ago

At this point, this is a feature that we do not require. The primary thought was that we could avoid the memory footprint of a new DistributedMatrix. The is solvable with more nodes.

pghysels commented 2 years ago

We have support for the HODLR (Hierarchically Off-Diagonal Low-Rank), and HODBF (Hierarchically Off-Diagonal Butterfly) formats. This requires STRUMPACK to be configured with support for ButterflyPACK. We can construct an HODLR or HODBF matrix from a matrix-vector product. So you can create an HODLR matrix using the structured::construct_matrix_free routine. This requires a matrix vector product routine as input, which applies the matrix (in this case given as a product of 2 matrices, say A*B) to a tall-skinny random matrix R. If both A and B are structured, you can implement this efficiently as A*(B*R).

AlexGKim commented 2 years ago

@pghysels . Thanks for letting us know about this functionality. While we do face this AQb where b is a vector, our more challenging problem is the product of AQA where A and Q are square. And as you see AQ appears multiple times in our problem. So my current implementation solves AQ, which is naturally structured, and multiplies it with A, which has is also structured. AQ is also the matrix that can be well approximated by a sparse matrix.

Our other thought was to Cholesky Q and work with that.

katlund commented 1 month ago

I recognize this is an old, closed issue... however, I am currently in need of the same functionality for HODLR matrices, and the A*(B*R) solution doesn't work for me, because I only have products of matrices, not their action on a vector or tall-skinny matrix. I've only been able to find these "StruMM" kernels implemented in prototyping toolboxes that aren't optimized. My end goal is to do performance studies against structure-agnostic sparse-sparse products.