{"id":{"repo_id":"uwo","oai_identifier":"oai:uwo.scholaris.ca:20.500.14721/33642"},"canonical_url":"https://search.dev.ndltd.org/etd/uwo/oai:uwo.scholaris.ca:20.500.14721/33642","repository":{"repo_id":"uwo","name":"Western University","base_url":"https://uwo.scholaris.ca/server/oai/request"},"display":{"title":"Efficient Algorithms and Parallel Implementations for Power Series Multiplication","abstract":"Power series play an important role in solving differential equations and approximating functions. A key operation in manipulating power series is their multiplication. Power series multiplication algorithms working based on a prescribed precision, say $n$ (where $n$ is a natural number), take the first $n$ coefficients of the two power series as input, multiply them, and return the first $n$ coefficients of the product. While these algorithms can be fast, they incur the overhead of recomputing known terms to enhance the product precision. On the other hand, lazy or relaxed multiplication algorithms compute the product terms incrementally. This allows for dynamic updates of product precision without the need to recompute the already known terms. In this thesis, we discuss efficient multiplication algorithms for univariate and multivariate power series, based on various schemes, including the Karatsuba algorithm, a novel partition multiplication technique using FFT, and an evaluation-interpolation strategy, along with their complexity analyses and parallelization opportunities. These algorithms and methods are implemented in C++ and integrated in the BPAS (Basic Polynomial Algebra Subprograms) library. To parallelize the implementations, we use a thread pool with a work-stealing scheduler using modern C++ multithreading techniques. The performance results, comparing the execution times of various algorithms in both serial and parallel modes, are presented and analyzed.","abstract_html":"Power series play an important role in solving differential equations and approximating functions. A key operation in manipulating power series is their multiplication. Power series multiplication algorithms working based on a prescribed precision, say $n$ (where $n$ is a natural number), take the first $n$ coefficients of the two power series as input, multiply them, and return the first $n$ coefficients of the product. While these algorithms can be fast, they incur the overhead of recomputing known terms to enhance the product precision. On the other hand, lazy or relaxed multiplication algorithms compute the product terms incrementally. This allows for dynamic updates of product precision without the need to recompute the already known terms. In this thesis, we discuss efficient multiplication algorithms for univariate and multivariate power series, based on various schemes, including the Karatsuba algorithm, a novel partition multiplication technique using FFT, and an evaluation-interpolation strategy, along with their complexity analyses and parallelization opportunities. These algorithms and methods are implemented in C++ and integrated in the BPAS (Basic Polynomial Algebra Subprograms) library. To parallelize the implementations, we use a thread pool with a work-stealing scheduler using modern C++ multithreading techniques. The performance results, comparing the execution times of various algorithms in both serial and parallel modes, are presented and analyzed.","abstract_has_math":true,"creators":["Fathi, Seyed Abdol Hamid"],"institution":"The University of Western Ontario","degree_name":"M Sc","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Moreno Maza, Marc"],"committee_chairs":[],"committee_members":[],"year":2024,"date_issued":"2024-08-28","date_published":"2024-08-28","updated_at":"2026-07-27T21:56:14Z","subjects":["Power series multiplication","Karatsuba","Fast Fourier Transform (FFT)","Parallel programming","C++","Multithreading","Thread pool","Divide-and-conquer","Partition multiplication","Evaluation-interpolation."],"languages":["en_ca"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14721/33642","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Moreno Maza, Marc"]},{"key":"dc:creator","label":"Author","values":["Fathi, Seyed Abdol Hamid"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-10T19:54:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-07-10T19:54:21Z"]},{"key":"dc:date.issued","label":"Date","values":["2024-08-28"]},{"key":"dc:publisher","label":"Institution","values":["The University of Western Ontario"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M Sc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Power series multiplication","Karatsuba","Fast Fourier Transform (FFT)","Parallel programming","C++","Multithreading","Thread pool","Divide-and-conquer","Partition multiplication","Evaluation-interpolation."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_ca"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14721/33642"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."]},{"key":"dc:description.abstract","label":"Abstract","values":["Power series play an important role in solving differential equations and approximating functions. A key operation in manipulating power series is their multiplication. Power series multiplication algorithms working based on a prescribed precision, say $n$ (where $n$ is a natural number), take the first $n$ coefficients of the two power series as input, multiply them, and return the first $n$ coefficients of the product. While these algorithms can be fast, they incur the overhead of recomputing known terms to enhance the product precision. On the other hand, lazy or relaxed multiplication algorithms compute the product terms incrementally. This allows for dynamic updates of product precision without the need to recompute the already known terms. In this thesis, we discuss efficient multiplication algorithms for univariate and multivariate power series, based on various schemes, including the Karatsuba algorithm, a novel partition multiplication technique using FFT, and an evaluation-interpolation strategy, along with their complexity analyses and parallelization opportunities. These algorithms and methods are implemented in C++ and integrated in the BPAS (Basic Polynomial Algebra Subprograms) library. To parallelize the implementations, we use a thread pool with a work-stealing scheduler using modern C++ multithreading techniques. The performance results, comparing the execution times of various algorithms in both serial and parallel modes, are presented and analyzed."]},{"key":"dc:title","label":"Title","values":["Efficient Algorithms and Parallel Implementations for Power Series Multiplication"]}]}],"canonical_facts":{"dc:contributor.advisor":["Moreno Maza, Marc"],"dc:creator":["Fathi, Seyed Abdol Hamid"],"dc:date.accessioned":["2025-07-10T19:54:21Z"],"dc:date.available":["2025-07-10T19:54:21Z"],"dc:date.issued":["2024-08-28"],"dc:description":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."],"dc:description.abstract":["Power series play an important role in solving differential equations and approximating functions. A key operation in manipulating power series is their multiplication. Power series multiplication algorithms working based on a prescribed precision, say $n$ (where $n$ is a natural number), take the first $n$ coefficients of the two power series as input, multiply them, and return the first $n$ coefficients of the product. While these algorithms can be fast, they incur the overhead of recomputing known terms to enhance the product precision. On the other hand, lazy or relaxed multiplication algorithms compute the product terms incrementally. This allows for dynamic updates of product precision without the need to recompute the already known terms. In this thesis, we discuss efficient multiplication algorithms for univariate and multivariate power series, based on various schemes, including the Karatsuba algorithm, a novel partition multiplication technique using FFT, and an evaluation-interpolation strategy, along with their complexity analyses and parallelization opportunities. These algorithms and methods are implemented in C++ and integrated in the BPAS (Basic Polynomial Algebra Subprograms) library. To parallelize the implementations, we use a thread pool with a work-stealing scheduler using modern C++ multithreading techniques. The performance results, comparing the execution times of various algorithms in both serial and parallel modes, are presented and analyzed."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14721/33642"],"dc:language.iso":["en_ca"],"dc:publisher":["The University of Western Ontario"],"dc:subject":["Power series multiplication","Karatsuba","Fast Fourier Transform (FFT)","Parallel programming","C++","Multithreading","Thread pool","Divide-and-conquer","Partition multiplication","Evaluation-interpolation."],"dc:title":["Efficient Algorithms and Parallel Implementations for Power Series Multiplication"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["M Sc"]},"updated_at":"2026-07-27T21:56:14Z"}