Implement Sparse Matrix Transposition and SMVP in Metal

[moven0831]

Problem

The accumulation phase of MSM can use sparse matrix transposition and Sparse Matrix-Vector Product (SMVP) operations for better efficiency. The current implementation does naive bucket accumulation.

Details

Develop efficient sparse matrix transposition and SMVP algorithms optimized for Metal. These optimizations will facilitate parallel bucket accumulation, thereby accelerating the MSM process on iOS devices.

Acceptance criteria

• Adapt the parallel transposition algorithm implemented in ZPrize 2023 Prize 2, Tal Derei and Koh Wei Jie, for Metal’s compute shaders, which is originally from the cuZK paper.
• Optimize memory access patterns within Metal shaders to reduce latency and improve throughput.
• Validate the correctness of transposition and SMVP operations through comprehensive testing.

Reference

• cuZK Paper - Sparse Matrix Transposition
• Parallel Transposition Techniques
• ZPrize 2023 Prize 2, Tal Derei and Koh Wei Jie