Abstract
CUMODP is a CUDA library for exact computations with dense polynomials over finite fields. A variety of operations like multiplication, division, computation of subresultants, multi-point evaluation, interpolation and many others are provided. These routines are primarily designed to offer GPU support to polynomial system solvers and a bivariate system solver is part of the library. Algorithms combine FFT-based and plain arithmetic, while the implementation strategy emphasizes reducing parallelism overheads and optimizing hardware usage.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. J. Symbolic Comput. 24(3-4), 235–265 (1997); Computational algebra and number theory (London, 1993)
Brent, R.P., Gaudry, P., Thomé, E., Zimmermann, P.: Faster multiplication in GF(2)[x]. In: van der Poorten, A.J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp. 153–166. Springer, Heidelberg (2008)
Frigo, M., Johnson, S.G.: The design and implementation of FFTW3 93(2), 216–231 (2005)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, New York (2003)
Gibbons, P.B.: A more practical PRAM model. In: Proc. of SPAA, pp. 158–168 (1989)
Gibbons, P.B., Matias, Y., Ramachandran, V.: The Queue-Read Queue-Write PRAM model: Accounting for contention in parallel algorithms. SIAM J. on Comput. 28(2), 733–769 (1998)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. on Applied Mathematics 17(2), 416–429 (1969)
Haque, S.A., Moreno Maza, M.: Plain polynomial arithmetic on GPU. J. of Physics: Conf. Series 385, 12014 (2012)
Haque, S.A., Moreno Maza, M., Xie, N.: A Many-core Machine Model for Designing Algorithms with Minimum Parallelism Overheads. Computing Research Repository, abs/1402.0264 (2014), http://arxiv.org/abs/1402.0264
Hart, W.B.: Fast library for number theory: An introduction. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) ICMS 2010. LNCS, vol. 6327, pp. 88–91. Springer, Heidelberg (2010)
Li, X., Moreno Maza, M., Rasheed, R., Schost, É.: The modpn library: Bringing fast polynomial arithmetic into maple. J. Symb. Comput. 46(7), 841–858 (2011)
Ma, L., Agrawal, K., Chamberlain, R.D.: A memory access model for highly-threaded many-core architectures. In: Proc. of ICPADS, pp. 339–347 (2012)
Moreno Maza, M., Pan, W.: Fast polynomial arithmetic on a gpu. J. of Physics: Conference Series 256 (2010)
Moreno Maza, M., Pan, W.: Solving bivariate polynomial systems on a gpu. J. of Physics: Conference Series 341 (2011)
Nickolls, J., Buck, I., Garland, M., Skadron, K.: Scalable parallel programming with CUDA. Queue 6(2), 40–53 (2008)
Püschel, M., Moura, J.M.F., Johnson, J., Padua, D., Veloso, M., Singer, B., Xiong, J., Franchetti, F., Gacic, A., Voronenko, Y., Chen, K., Johnson, R.W., Rizzolo, N.: SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, Special issue on “Program Generation, Optimization, and Adaptation” 93(2), 232–275 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Haque, S.A., Li, X., Mansouri, F., Maza, M.M., Pan, W., Xie, N. (2014). Dense Arithmetic over Finite Fields with the CUMODP Library. In: Hong, H., Yap, C. (eds) Mathematical Software – ICMS 2014. ICMS 2014. Lecture Notes in Computer Science, vol 8592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44199-2_108
Download citation
DOI: https://doi.org/10.1007/978-3-662-44199-2_108
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44198-5
Online ISBN: 978-3-662-44199-2
eBook Packages: Computer ScienceComputer Science (R0)