{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T22:11:48Z","timestamp":1761948708430,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,18]]},"DOI":"10.1145\/3452143.3465511","type":"proceedings-article","created":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T22:32:21Z","timestamp":1626215541000},"page":"15-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Design and Implementation of Multi-Threaded Algorithms in Polynomial Algebra"],"prefix":"10.1145","author":[{"given":"Marc","family":"Moreno Maza","sequence":"first","affiliation":[{"name":"University of Western Ontario, London, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1974","unstructured":"Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company."},{"key":"e_1_3_2_1_2_1","unstructured":"M. Asadi A. Brandt C. Chen S. Covanov F. Mansouri D. Mohajerani R. H. C. Moir M. Moreno Maza D. Talaashrafi Linxiao Wang Ning Xie and Yuzhen Xie. 2021. Basic Polynomial Algebra Subprograms (BPAS). www.bpaslib.org."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3390\/math7050441"},{"key":"e_1_3_2_1_4_1","volume-title":"Marc Moreno Maza, and Yuzhen Xie","author":"Asadi Mohammadali","year":"2021","unstructured":"Mohammadali Asadi, Alexander Brandt, Robert H. C. Moir, Marc Moreno Maza, and Yuzhen Xie. 2021. Parallelization of Triangular Decompositions: Techniques and Implementation. J. Symb. Comput. (2021). (to appear)."},{"key":"e_1_3_2_1_5_1","first-page":"1","article-title":"Strategy-Accurate Parallel Buchberger Algorithms","volume":"22","author":"Attardi Giuseppe","year":"1996","unstructured":"Giuseppe Attardi and Carlo Traverso. 1996. Strategy-Accurate Parallel Buchberger Algorithms. J. Symbolic Computation 22 (1996), 1--15.","journal-title":"J. Symbolic Computation"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025127.1025992"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"volume-title":"Principles of concurrent and distributed programming","author":"Ben-Ari Mordechai","key":"e_1_3_2_1_8_1","unstructured":"Mordechai Ben-Ari. 1990. Principles of concurrent and distributed programming. Prentice Hall."},{"key":"e_1_3_2_1_9_1","series-title":"SIAM review 59, 1","volume-title":"Julia: A fresh approach to numerical computing","author":"Bezanson Jeff","year":"2017","unstructured":"Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. 2017. Julia: A fresh approach to numerical computing. SIAM review 59, 1 (2017), 65--98."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/96877.96965"},{"volume-title":"High Performance Sparse Multivariate Polynomials: Fundamental Data Structures and Algorithms. Master's thesis","author":"Brandt Alexander","key":"e_1_3_2_1_12_1","unstructured":"Alexander Brandt. 2018. High Performance Sparse Multivariate Polynomials: Fundamental Data Structures and Algorithms. Master's thesis. Western University."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85165-1_6"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the Japanese Symposium on functional programming. 54--61","author":"Buchberger Bruno","year":"1987","unstructured":"Bruno Buchberger. 1987. The parallelization of critical-pair\/completion procedures on the L-Machine. In Proceedings of the Japanese Symposium on functional programming. 54--61."},{"key":"e_1_3_2_1_15_1","volume-title":"Parallel Integer Polynomial Multiplication. In 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016","author":"Chen Changbo","year":"2016","unstructured":"Changbo Chen, Svyatoslav Covanov, Farnam Mansouri, Marc Moreno Maza, Ning Xie, and Yuzhen Xie. 2016. Parallel Integer Polynomial Multiplication. In 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016, Timisoara, Romania, September 24-27, 2016. 72--80."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.11.008"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.12.023"},{"key":"e_1_3_2_1_18_1","first-page":"12","article-title":"Cache Complexity and Multicore Implementation for Univariate Real Root Isolation","volume":"341","author":"Chen Changbo","year":"2011","unstructured":"Changbo Chen, Marc Moreno Maza, and Yuzhen Xie. 2011. Cache Complexity and Multicore Implementation for Univariate Real Root Isolation. J. of Physics: Conference Series 341 (2011), 12.","journal-title":"J. of Physics: Conference Series"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3663508"},{"key":"e_1_3_2_1_20_1","volume-title":"Big Prime Field FFT on Multi-core Processors. In International Symposium on Symbolic and Algebraic Computation (ISSAC '19)","author":"Covanov Svyatoslav","year":"2019","unstructured":"Svyatoslav Covanov, Davood Mohajerani, Marc Moreno Maza, and Lin-Xiao Wang. 2019. Big Prime Field FFT on Multi-core Processors. In International Symposium on Symbolic and Algebraic Computation (ISSAC '19), Beijing, China, July 15-18, 2019. 106--113."},{"key":"e_1_3_2_1_21_1","volume-title":"First International Workshop","author":"Dora Jean Della","year":"1988","unstructured":"Jean Della Dora and John Fitch (Eds.). 1988. Computer Algebra and Parallelism, First International Workshop, Grenoble, France, September 1989. Academic Press."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790282"},{"volume-title":"Elementary matrix theory","author":"Eves Howard Whitley","key":"e_1_3_2_1_23_1","unstructured":"Howard Whitley Eves. 1980. Elementary matrix theory. Courier Corporation."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2006.1620789"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837225"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 2017 International Workshop on Parallel Symbolic Computation, PASCO 2017","author":"Faug\u00e8re Jean-Charles","year":"2017","unstructured":"Jean-Charles Faug\u00e8re, Michael B. Monagan, and Hans-Wolfgang Loidl (Eds.). 2017. Proceedings of the 2017 International Workshop on Parallel Symbolic Computation, PASCO 2017, Kaiserslautern, Germany, July 23-24, 2017. ACM."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148157"},{"volume-title":"Computer Algebra in Scientific Computing (CASC '13) (LNCS)","author":"Gastineau Micka\u00ebl","key":"e_1_3_2_1_29_1","unstructured":"Micka\u00ebl Gastineau and Jacques Laskar. 2013. Highly Scalable Multiplication for Distributed Sparse Multivariate Polynomials on Many-Core Systems. In Computer Algebra in Scientific Computing (CASC '13) (LNCS), Vol. 8136. Springer, 100--115."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790282.2790285"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.09.012"},{"key":"e_1_3_2_1_32_1","volume-title":"Marc Moreno Maza, and Ning Xie","author":"Haque Sardar Anisul","year":"2014","unstructured":"Sardar Anisul Haque, Marc Moreno Maza, and Ning Xie. 2014. A Many-core Machine Model for Designing Algorithms with Minimum Parallelism Overheads. CoRR abs\/1402.0264 (2014). arXiv:1402.0264 http:\/\/arxiv.org\/abs\/1402.0264"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the International Conference on Parallel Computing, ParCo 2015","volume":"27","author":"Haque Sardar Anisul","year":"2015","unstructured":"Sardar Anisul Haque, Marc Moreno Maza, and Ning Xie. 2015. A Many-Core Machine Model for Designing Algorithms with Minimum Parallelism Overheads. In Parallel Computing: On the Road to Exascale, Proceedings of the International Conference on Parallel Computing, ParCo 2015, 1-4 September 2015, Edinburgh, Scotland, UK (Advances in Parallel Computing), Vol. 27. IOS Press, 35--44."},{"key":"e_1_3_2_1_34_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2012","unstructured":"John L. Hennessy and David A. Patterson. 2012. Computer Architecture - A Quantitative Approach, 5th Edition. Morgan Kaufmann.","edition":"5"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263716"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","DOI":"10.1142\/2546","volume-title":"Proceedings of the 1st International Workshop on Parallel Symbolic Computation, PASCO","author":"Ed Hoon Hong","year":"1994","unstructured":"Hoon Hong (Ed.). 1994. Proceedings of the 1st International Workshop on Parallel Symbolic Computation, PASCO 1994, Linz, Austria. World scientific."},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 2nd International Workshop on Parallel Symbolic Computation, PASCO 1997","author":"Hong Hoon","year":"1997","unstructured":"Hoon Hong, Erich Kaltofen, and Markus A. Hitz (Eds.). 1997. Proceedings of the 2nd International Workshop on Parallel Symbolic Computation, PASCO 1997, July 20--22, 1997, Kihei, Hawaii, USA. ACM."},{"key":"e_1_3_2_1_38_1","volume-title":"ISCA","author":"Hong Sunpyo","year":"2009","unstructured":"Sunpyo Hong and Hyesoon Kim. 2009. An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness. In ISCA 2009. 152--163."},{"key":"e_1_3_2_1_39_1","volume-title":"Wolf","author":"Lam Monica S.","year":"1991","unstructured":"Monica S. Lam, Edward E. Rothberg, and Michael E. Wolf. 1991. The Cache Performance and Optimizations of Blocked Algorithms. In ASPLOS-IV Proceedings. ACM Press, 63--74."},{"volume-title":"Encyclopedia of Parallel Computing. 273--288.","author":"Leiserson Charles E.","key":"e_1_3_2_1_40_1","unstructured":"Charles E. Leiserson. 2011. Cilk. In Encyclopedia of Parallel Computing. 273--288."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2747903.2748175"},{"key":"e_1_3_2_1_42_1","volume-title":"23rd International Symposium, HPCS 2009 (LNCS)","volume":"5976","author":"Maza Marc Moreno","year":"2009","unstructured":"Marc Moreno Maza and Yuzhen Xie. 2009. FFT-Based Dense Polynomial Arithmetic on Multi-cores. In High Performance Computing Systems and Applications, 23rd International Symposium, HPCS 2009 (LNCS), Vol. 5976. Springer, 378--399."},{"volume-title":"Structured parallel programming: patterns for efficient computation","author":"McCool Michael","key":"e_1_3_2_1_43_1","unstructured":"Michael McCool, James Reinders, and Arch Robison. 2012. Structured parallel programming: patterns for efficient computation. Elsevier."},{"key":"e_1_3_2_1_44_1","volume-title":"International Symposium on Symbolic and Algebraic Computation, (ISSAC '09)","author":"Michael","year":"2009","unstructured":"Michael B. Monagan and Roman Pearce. 2009. Parallel sparse polynomial multiplication using heaps. In International Symposium on Symbolic and Algebraic Computation, (ISSAC '09), Seoul, Republic of Korea, July 29-31, 2009. ACM."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.08.014"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the 4th International Workshop on Parallel Symbolic Computation, PASCO 2010","author":"Maza Marc Moreno","year":"2010","unstructured":"Marc Moreno Maza and Jean-Louis Roch (Eds.). 2010. Proceedings of the 4th International Workshop on Parallel Symbolic Computation, PASCO 2010, July 21-23, 2010, Grenoble, France. ACM."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278177"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111008556"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365490.1365500"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384256"},{"volume-title":"Models of computation - exploring the power of computing","author":"Savage John E.","key":"e_1_3_2_1_52_1","unstructured":"John E. Savage. 1998. Models of computation - exploring the power of computing. Addison-Wesley."},{"key":"e_1_3_2_1_53_1","volume-title":"PPOPP 2012","author":"Sim Jaewoong","year":"2012","unstructured":"Jaewoong Sim, Aniruddha Dasgupta, Hyesoon Kim, and Richard W. Vuduc. 2012. A performance analysis framework for identifying potential benefits in GPGPU applications. In PPOPP 2012, New Orleans, LA, USA, February 25--29, 2012."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Charles Van Loan. 1992. Computational frameworks for the fast Fourier transform. SIAM.","DOI":"10.1137\/1.9781611970999"},{"volume-title":"Modern Computer Algebra (3. ed.)","author":"von zur Gathen Joachim","key":"e_1_3_2_1_55_1","unstructured":"Joachim von zur Gathen and J\u00fcrgen Gerhard. 2013. Modern Computer Algebra (3. ed.). Cambridge University Press."},{"key":"e_1_3_2_1_56_1","volume-title":"EUROCAL '87, Proceedings (LNCS)","volume":"378","year":"1987","unstructured":"Wen-tsun Wu. 1987. A zero structure theorem for polynomial-equations-solving and its applications. In EUROCAL '87, Proceedings (LNCS), Vol. 378. Springer, 44."},{"key":"e_1_3_2_1_57_1","volume-title":"Second International Workshop","volume":"584","author":"Ed Richard Zippel","year":"1992","unstructured":"Richard Zippel (Ed.). 1992. Computer Algebra and Parallelism, Second International Workshop, Ithaca, USA, May 9--11, 1990. LNCS, Vol. 584. Springer"}],"event":{"name":"ISSAC '21: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Virtual Event Russian Federation","acronym":"ISSAC '21"},"container-title":["Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452143.3465511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452143.3465511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:07Z","timestamp":1750193287000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452143.3465511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":55,"alternative-id":["10.1145\/3452143.3465511","10.1145\/3452143"],"URL":"https:\/\/doi.org\/10.1145\/3452143.3465511","relation":{},"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"2021-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}