Metraipolis › archive › dc_98dd74e41450

Accelerating Multiple-Precision LU Decomposition with Ozaki Scheme II — arXiv:2609.29554

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29554
License (as archived)
CC0-1.0
Archived
2026-10-08T06:08:21.848Z
SHA-256 of the archived text
17ac09240bd1c8d55efa4f58d0e24c10d691ba0cc247b00bead022d6778ac584
Stable URL of this page
https://metraipolis.com/documento/dc_98dd74e41450

How to cite

Accelerating Multiple-Precision LU Decomposition with Ozaki Scheme II — arXiv:2609.29554 — arXiv (en), https://arxiv.org/abs/2609.29554 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_98dd74e41450 (Metraipolis archive dc_98dd74e41450, sha256 17ac09240bd1c8d55efa4f58d0e24c10d691ba0cc247b00bead022d6778ac584)
BibTeX
@misc{dc98dd74e41450,
  title = {Accelerating Multiple-Precision LU Decomposition with Ozaki Scheme II — arXiv:2609.29554},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29554},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_98dd74e41450; sha256 17ac09240bd1c8d55efa4f58d0e24c10d691ba0cc247b00bead022d6778ac584},
  year = {2026}
}

Archived text

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

Solving ill-conditioned linear systems needs LU decomposition in precisions beyond binary64. The standard approaches -- GMP/MPFR, or multi-component arithmetic such as double-double -- leave every scalar multiply-add inside the O(n^3) update in multiple precision, and so cannot exploit the low-precision matrix engines that dominate current hardware. We build a blocked, partially pivoted LU decomposition on Ozaki scheme II, which replaces the multiple-precision GEMM by exact integer modular products followed by an explicit CRT reconstruction, and implement it for multi-component (DD/TD/QD) and arbitrary precision, on CPUs and GPUs. Two contributions make this practical: a direct conversion between the non-overlapping expansion format and the internal fixed-point representation, which removes the MPFR round trip and is worth a factor of 2.4--4.7; and new FP16, FP8 and binary64 GPU back-ends, the FP8 one using a balanced base-17 two-digit encoding that keeps the full 362.8-bit CRT capacity of INT8. On an Arm/GB10 and an x86/H100 the fastest back-end changes with the machine: INT8 wins on GB10, whereas on H100 binary64 is fastest for QD, beating both the native implementation and INT8. The essential point of Ozaki scheme II is thus not to use a low-precision engine but to choose the format maximising bits-per-modulus times engine throughput. For the Lotkin matrix at p ~ 1.2 log2 cond(A) we reach relative errors of 10^-645 at n=2048, up to 2.84x faster than a fully OpenMP-parallel multiple-precision LU. We also show by measurement that the O(p) advantage of scheme II over scheme I applies only to the GEMM term: modular reduction and CRT grow as O(p^2) and dominate the runtime at the matrix sizes considered here. The implementation is released as open source.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in math.NA).
Categorie arXiv: Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2609.29554 — 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-08T05:35:20.327Z dalla pagina https://arxiv.org/catchup/math.NA/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).