A C implementation of the Smith massager algorithm

Ziwen Wang; Stavros Birmpilis; George Labahn; Arne Storjohann

A C implementation of the Smith massager algorithm

Ziwen Wang, Stavros Birmpilis, George Labahn, Arne Storjohann

arXivarxiv/2605.19254May 19, 2026cs.MSscore 0

We describe a C implementation of the Las Vegas algorithm of Birmpilis, Labahn and Storjohann from 2020 for computing the Smith normal form of a nonsingular integer matrix. The algorithm computes a Smith massager for the input matrix using $O(n^ω\, \B(\log n + \log \|A\|)\, (\log n)^2)$ bit operations, which is softly equivalent to the cost of multiplying two matrices of the same dimension and entry size. We describe the key implementation techniques that bridge the gap between the theoretical algorithm and practical performance, including BLAS-accelerated modular arithmetic via the Residue…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.19254
curl -X POST /api/v1/records/arxiv/2605.19254/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.19254/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'