×

Rings: an efficient Java/Scala library for polynomial rings. (English) Zbl 07682918

Summary: In this paper we briefly discuss Rings – an efficient lightweight library for commutative algebra. Polynomial arithmetic, GCDs, polynomial factorization and Gröbner bases are implemented with the use of modern asymptotically fast algorithms. Rings can be easily interacted or embedded in applications in high-energy physics and other research areas via a simple API with fully typed hierarchy of algebraic structures and algorithms for commutative algebra. The use of the Scala language brings a quite novel powerful, strongly typed functional programming model allowing to write short, expressive, and fast code for applications. At the same time Rings shows one of the best performances among existing software for algebraic calculations.

MSC:

65Y15 Packaged methods for numerical algorithms
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13-04 Software, source code, etc. for problems pertaining to commutative algebra
81-04 Software, source code, etc. for problems pertaining to quantum theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Larsen, K. J.; Zhang, Y., Phys. Rev., D93, 4, 041701 (2016), arXiv:1511.01071
[2] Larsen, K. J.; Rietkerk, R., Comput. Phys. Comm., 222, 250-262 (2018), arXiv:1701.01040 · Zbl 07693048
[3] Meyer, C., J. High Energy Phys., 04, 006 (2017), arXiv:1611.01087
[4] von Manteuffel, A.; Schabinger, R. M., Phys. Lett., B744, 101-104 (2015), arXiv:1406.4513 · Zbl 1330.81151
[5] Acar, A.; Aksu, H.; Selcuk Uluagac, A.; Conti, M., CoRR, abs/1704.03578 (2017), arXiv:1704.03578
[6] Kondor, R., Group Theoretical Methods in Machine Learning (2008), Columbia University, (Ph.D. thesis)
[7] W. Decker, G.-M. Greuel, G. Pfister, H. Schönemann, Singular 4-1-0 —A computer algebra system for polynomial computations, 2016. http://www.singular.uni-kl.de.
[8] V. Shoup, NTL: A library for doing number theory, 2018. http://www.shoup.net/ntl.
[9] W. Hart, F. Johansson, S. Pancratz, FLINT: Fast library for number theory, 2018. http://flintlib.org.
[10] Bauer, C.; Frink, A.; Kreckel, R., J. Symbolic Comput., 33, 1, 1-12 (2002), https://www.ginac.de · Zbl 1017.68163
[11] Kuipers, J.; Ueda, T.; Vermaseren, J. A.M.; Vollinga, J., Comput. Phys. Comm., 184, 1453-1467 (2013), arXiv:1203.6543 · Zbl 1317.68286
[12] B. Ruijl, T. Ueda, J. Vermaseren, FORM version 4.2, 2017. arXiv:1707.06453.
[13] Smirnov, A. V., J. High Energy Phys., 10, 107 (2008), arXiv:0807.3243
[14] A. von Manteuffel, C. Studerus, Reduze 2 - Distributed Feynman Integral Reduction, 2012. arXiv:1201.4330.
[15] R. Lewis, Computer algebra system fermat, 2018. http://home.bway.net/lewis.
[16] T. Daly, Axiom: The scientific computation system, 2018. http://www.axiom-developer.org.
[17] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press · Zbl 1055.68168
[18] Feng, F., Comput. Phys. Comm., 183, 2158-2164 (2012), arXiv:1204.2314 · Zbl 1296.81007
[19] A. Raichev, Leinartas’s partial fraction decomposition, arxiv e-prints, 2012. arXiv:1206.4740.
[20] Faugère, J. C., (Fukuda Komeiand Hoeven, M. T.N., Mathematical Software -ICMS 2010 (2010), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 84-87
[21] T. Coladon, V. Vitse, A. Joux, OpenF4 implementation, 2018. https://github.com/nauotit/openf4.
[22] Granlund, T.; the GMP development team, GNU MP: The GNU Multiple Precision Arithmetic Library (2017), http://gmplib.org/
[23] Knuth, D. E., The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms (1997), Addison Wesley Longman Publishing Co., Inc.: Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA, Section 4.3.3 · Zbl 0895.68055
[24] Barrett, P., (Odlyzko, A. M., Advances in Cryptology —CRYPTO’ 86: Proceedings (1987), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 311-323
[25] Fog, A., Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs (2017), http://www.agner.org/optimize/instruction_tables.pdf
[26] Warren, H. S., Hacker’s Delight (2012), Addison Wesley - Pearson Education, Inc.
[27] Miller, G. L., (Proceedings of the Seventh Annual ACM Symposium on Theory of Computing. Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, STOC ’75 (1975), ACM: ACM New York, NY, USA), 234-239
[28] Rabin, M. O., J. Number Theory, 12, 1, 128-138 (1980) · Zbl 0426.10006
[29] Pollard, J. M., BIT Numer. Math., 15, 3, 331-334 (1975) · Zbl 0312.10006
[30] Pollard, J. M., Math. Proc. Camb. Phil. Soc., 76, 3, 521-528 (1974) · Zbl 0294.10005
[31] Pomerance, C., Mathematisch Centrum Computational Methods in Number Theory (1982), Pt. 1 P 89-139(SEE N 84-17990 08-67)
[32] Crandall, R.; Pomerance, C., (Prime Numbers: A Computational Perspective. Prime Numbers: A Computational Perspective, Lecture Notes in Statistics (2006), Springer New York)
[33] Atkin, A.; Bernstein, D., Math. Comp., 73, 1023-1030 (2004) · Zbl 1049.11137
[34] Brown, W. S., J. ACM, 18, 4, 478-504 (1971) · Zbl 0226.65040
[35] Langemyr, L.; McCallum, S., J. Symbolic Comput., 8, 5, 429-448 (1989) · Zbl 0689.68042
[36] Encarnación, M. J., J. Symbolic Comput., 20, 3, 299-313 (1995) · Zbl 0855.68046
[37] Cantor, D. G.; Zassenhaus, H., Math. Comp., 36, 154, 587-592 (1981) · Zbl 0493.12024
[38] Shoup, V., J. Symbolic Comput., 4, 20, 363-397 (1995) · Zbl 0854.11074
[39] Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithms for computer algebra (1992), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA · Zbl 0805.68072
[40] Zippel, R., Effective Polynomial Computation (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0794.11048
[41] van Hoeij, M., J. Number Theory, 95, 2, 167-189 (2002) · Zbl 1081.11080
[42] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Math. Ann., 261, 4, 515-534 (1982) · Zbl 0488.12001
[43] Trager, B. M., (Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation. Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation, SYMSAC ’76 (1976), ACM: ACM New York, NY, USA), 219-226 · Zbl 0498.12005
[44] Monagan, M.; Pearce, R., ACM Commun. Comput. Algebra, 44, 3/4, 205-209 (2011) · Zbl 1308.68183
[45] Zippel, R., Proceedings of the International Symposiumon on Symbolic and Algebraic Computation EUROSAM’79, 216-226 (1979), Springer-Verla: Springer-Verla London, UK
[46] de Kleine, J.; Monagan, M. B.; Wittkopf, A. D., Proceeding of ISSAC’05, 124-131 (2005), ACM Press
[47] Wang, P. S., ACM SIGSAM Bull., 14, 50-60 (1980) · Zbl 0445.68026
[48] Kaltofen, E.; Monagan, M. B., Proceeding of ISSAC’99, 59-66 (1999), ACM Press
[49] Moses, J.; Yun, D. Y.Y., Proceeding of ACM Annual Conference, 159-166 (1973), ACM
[50] Kaltofen, E., Proceeding of EUROCAL’85, vol. 2, 4-17 (1985), Comput. Algebra Proc. · Zbl 0605.12011
[51] Lee, M. M.D., Factorization of Multivariate Polynomials (2013), University of Kaiserslautern, (Ph.D. thesis)
[52] Bernardin, L.; Monagan, M., (Proceeding of AAECC’97, vol. 1255. Proceeding of AAECC’97, vol. 1255, Lecture Notes in Computer Science (1997), Springer: Springer Berlin, Heidelberg), 15-28
[53] Bernardin, L., Factorization of Multivariate Polynomials over Finite Fields (1999), ETH Zurich, (Ph.D. thesis)
[54] Gao, S., J. Algebra, 237, 2, 501-520 (2001) · Zbl 0997.12001
[55] Gebauer, R.; Möller, H. M., J. Symbolic Comput., 6, 2, 275-286 (1988) · Zbl 0675.13013
[56] Becker, T.; Weispfenning, V.; Kredel, H., Graduate Texts in Mathematics (1993), Springer-Verlag · Zbl 0772.13010
[57] Faugére, J., J. Pure Appl. Algebra, 139, 1, 61-88 (1999) · Zbl 0930.68174
[58] Faugère, J.; Lachartre, S., (Proceedings of the 4th International Workshop on Parallel and Symbolic Computation. Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, PASCO ’10 (2010), ACM: ACM New York, NY, USA), 89-97
[59] Joux, A.; Vitse, V., Topics in Cryptology -CT-RSA 2011, 356-375 (2011), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[60] Traverso, C., J. Symbolic Comput., 22, 4, 355-376 (1996) · Zbl 0922.13019
[61] Buchberger, B., SIGSAM Bull., 10, 3, 19-29 (1976)
[62] Arnold, E. A., J. Symbolic Comput., 35, 4, 403-419 (2003) · Zbl 1046.13018
[63] Cox, D.; Little, J.; O’Shea, D., (Undergraduate Texts in Mathematics (2008), Springer New York)
[64] Giovini, A.; Mora, T.; Niesi, G.; Robbiano, L.; Traverso, C., (Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC ’91 (1991), ACM: ACM New York, NY, USA), 49-54 · Zbl 0933.68161
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.