Rational number reconstruction using Chinese remainder theorem on GPU

Toru Fukaya; Tomoyuki Idogawa

doi:10.1109/ICIS.2016.7550900

Rational number reconstruction using Chinese remainder theorem on GPU

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The purpose of this study is to make rational number arithmetic fast. For this purpose, we implemented a rational number reconstruction method, a kind of modular algorithms, in which we used Chinese remainder theorem in order to parallelize calculation. We implemented it on CPU and GPU. Then, we applied them to some examples of computing such as inner products, Frobenius normal forms of matrices and determinants of matrices to examine their efficiencies. As a result, we showed that our implementations calculated faster than the standard arithmetic by using GMP at least in the latter two cases (i.e., computing of Frobenius normal forms and determinants). We also showed that the GPU version calculated 8.3 times faster at most than the CPU version.

Original language	English
Title of host publication	2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781509008063
DOIs	https://doi.org/10.1109/ICIS.2016.7550900
Publication status	Published - 2016 Aug 23
Event	15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016 - Okayama, Japan Duration: 2016 Jun 26 → 2016 Jun 29

Other

Other	15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016
Country/Territory	Japan
City	Okayama
Period	16/6/26 → 16/6/29

ASJC Scopus subject areas

Computer Science(all)
Energy Engineering and Power Technology
Control and Optimization

Access to Document

10.1109/ICIS.2016.7550900

Cite this

Rational number reconstruction using Chinese remainder theorem on GPU. / Fukaya, Toru; Idogawa, Tomoyuki.

2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2016. 7550900.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fukaya, T & Idogawa, T 2016, Rational number reconstruction using Chinese remainder theorem on GPU. in 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings., 7550900, Institute of Electrical and Electronics Engineers Inc., 15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016, Okayama, Japan, 16/6/26. https://doi.org/10.1109/ICIS.2016.7550900

@inproceedings{f44b611e93344bf595916d2ad719118b,

title = "Rational number reconstruction using Chinese remainder theorem on GPU",

abstract = "The purpose of this study is to make rational number arithmetic fast. For this purpose, we implemented a rational number reconstruction method, a kind of modular algorithms, in which we used Chinese remainder theorem in order to parallelize calculation. We implemented it on CPU and GPU. Then, we applied them to some examples of computing such as inner products, Frobenius normal forms of matrices and determinants of matrices to examine their efficiencies. As a result, we showed that our implementations calculated faster than the standard arithmetic by using GMP at least in the latter two cases (i.e., computing of Frobenius normal forms and determinants). We also showed that the GPU version calculated 8.3 times faster at most than the CPU version.",

author = "Toru Fukaya and Tomoyuki Idogawa",

year = "2016",

month = aug,

day = "23",

doi = "10.1109/ICIS.2016.7550900",

language = "English",

booktitle = "2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016 ; Conference date: 26-06-2016 Through 29-06-2016",

}

TY - GEN

T1 - Rational number reconstruction using Chinese remainder theorem on GPU

AU - Fukaya, Toru

AU - Idogawa, Tomoyuki

PY - 2016/8/23

Y1 - 2016/8/23

N2 - The purpose of this study is to make rational number arithmetic fast. For this purpose, we implemented a rational number reconstruction method, a kind of modular algorithms, in which we used Chinese remainder theorem in order to parallelize calculation. We implemented it on CPU and GPU. Then, we applied them to some examples of computing such as inner products, Frobenius normal forms of matrices and determinants of matrices to examine their efficiencies. As a result, we showed that our implementations calculated faster than the standard arithmetic by using GMP at least in the latter two cases (i.e., computing of Frobenius normal forms and determinants). We also showed that the GPU version calculated 8.3 times faster at most than the CPU version.

AB - The purpose of this study is to make rational number arithmetic fast. For this purpose, we implemented a rational number reconstruction method, a kind of modular algorithms, in which we used Chinese remainder theorem in order to parallelize calculation. We implemented it on CPU and GPU. Then, we applied them to some examples of computing such as inner products, Frobenius normal forms of matrices and determinants of matrices to examine their efficiencies. As a result, we showed that our implementations calculated faster than the standard arithmetic by using GMP at least in the latter two cases (i.e., computing of Frobenius normal forms and determinants). We also showed that the GPU version calculated 8.3 times faster at most than the CPU version.

UR - http://www.scopus.com/inward/record.url?scp=84988009603&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988009603&partnerID=8YFLogxK

U2 - 10.1109/ICIS.2016.7550900

DO - 10.1109/ICIS.2016.7550900

M3 - Conference contribution

AN - SCOPUS:84988009603

BT - 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016

Y2 - 26 June 2016 through 29 June 2016

ER -

Rational number reconstruction using Chinese remainder theorem on GPU

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this