Simultaneous Conversions with the Residue Number System Using Linear Algebra

被引：5

作者：

Doliskani, Javad ^{[1
]}

Giorgi, Pascal ^{[2
,3
]}

Lebreton, Romain ^{[2
,3
]}

Schost, Eric

机构：

[1] Univ Waterloo, Inst Quantum Comp, 200 Univ Ave, Waterloo, ON N2L 3G1, Canada

[2] Univ Waterloo, 200 Univ Ave, Waterloo, ON N2L 3G1, Canada

[3] Univ Montpellier, CNRS, LIRMM, 161 Rue Ada, F-34095 Montpellier 5, France

来源：

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE | 2018年 / 44卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Chinese Remainder Theorem; Residue Number System; integer matrix multiplication; integer polynomial multiplication; linear algebra library; multiprecision arithmetic; POLYNOMIAL FACTORIZATION; ALGORITHM; MULTIPLICATION;

D O I：

10.1145/3145573

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an algorithm for simultaneous conversions between a given set of integers and their Residue Number System representations based on linear algebra. We provide a highly optimized implementation of the algorithm that exploits the computational features of modern processors. The main application of our algorithm is matrix multiplication over integers. Our speed-up of the conversions to and from the Residue Number System significantly improves the overall running time of matrix multiplication.

引用

页数：21

共 46 条

[1]

Aho Alfred V., 1974, The Design and Analysis of Computer Algorithms

[2]

[Anonymous], INT MATH KERN LIB

[3]

[Anonymous], 2013, MODERN COMPUTER ALGE

[4]

[Anonymous], 2010, Modern Computer Arithmetic, DOI DOI 10.1017/CBO9780511921698

[5]

BARRETT P, 1987, LECT NOTES COMPUT SC, V263, P311

[6]

Bernstein D.J., 2004, Scaled remainder trees

[7] FAST MODULAR TRANSFORMS [J].

BORODIN, A ;

MOENCK, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 8 (03) :366-386

[8]

Bosma W., 1997, J SYMB COMPUT, V24, P3, DOI DOI 10.1006/JSC0.1996.0125

[9] FAST ALGORITHMS FOR MANIPULATING FORMAL POWER-SERIES [J].

BRENT, RP ;

KUNG, HT .

JOURNAL OF THE ACM, 1978, 25 (04) :581-595

[10]

CANTOR DG, 1981, MATH COMPUT, V36, P587, DOI 10.1090/S0025-5718-1981-0606517-5

← 1 2 3 4 5 →