Metraipolis › archive › dc_70525b07feaf

The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering — arXiv:2608.15390

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.15390
License (as archived): CC0-1.0
Archived: 2026-10-19T00:11:28.201Z
SHA-256 of the archived text: ae387d7e2ba60284468ae3b257ab08258a8c6db54c4732ebbd5c9c9a3d29448b
Stable URL of this page: https://metraipolis.com/documento/dc_70525b07feaf

How to cite

The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering — arXiv:2608.15390 — arXiv (en), https://arxiv.org/abs/2608.15390 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_70525b07feaf (Metraipolis archive dc_70525b07feaf, sha256 ae387d7e2ba60284468ae3b257ab08258a8c6db54c4732ebbd5c9c9a3d29448b)

BibTeX

@misc{dc70525b07feaf,
  title = {The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering — arXiv:2608.15390},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.15390},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_70525b07feaf; sha256 ae387d7e2ba60284468ae3b257ab08258a8c6db54c4732ebbd5c9c9a3d29448b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15390. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, they do not directly address the choice of the next vertex. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with O(n + m) total bucket-maintenance work per trajectory, where n is the number of rows/columns in the matrix and m is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show that it is competitive with the state of the art on the tested small matrices and scales effectively to large sparse matrices.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.15390 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T23:35:27.564Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).