Parallel polynomial operations on SMPs: an overview
---

Title: Parallel polynomial operations on SMPs: an overview

Section 1: Introduction
Description 1: Provide a brief introduction to the topic of parallel polynomial operations on Symmetric Multiprocessing (SMP) systems, including the significance and applications of the topic.

Section 2: Parallel PFACTOR Package
Description 2: Describe the Parallel PFACTOR package, including its functionalities such as parallel selection of primes, automatic balancing of work, parallel Berlekamp algorithm, and parallel reconciliation of degrees.

Section 3: Load Balancing
Description 3: Discuss the importance of load balancing in the parallel PFACTOR package, including how parameters like the number of processes and primes are used to control parallel activities effectively.

Section 4: Parallel Berlekamp Algorithm
Description 4: Explain the parallel Berlekamp algorithm, detailing its input requirements, the formation of the matrix, null space basis computation, and parallel GCD computations.

Section 5: Parallel Degree Reconciliation
Description 5: Discuss the method of parallel degree reconciliation after factoring modulo different primes, including the analysis of degree compatibility and the grouping of extraneous factors.

Section 6: Univariate p-adic Lifting
Description 6: Describe the univariate p-adic lifting process, including key computations and parallelization strategies for various steps involved in the lifting procedure.

Section 7: Parallel Polynomial Arithmetic
Description 7: Explain parallel polynomial arithmetic, including different algorithms for polynomial multiplication and their suitability for parallelization on SMPs.

Section 8: Multivariate p-adic Lifting
Description 8: Detail the parallelization of multivariate p-adic lifting, including the algorithmic steps and parallel strategies for lifting in multiple variables.

Section 9: Sparse Multivariate GCD
Description 9: Summarize the parallel GCD algorithms for sparse multivariate polynomials and the strategies for exploiting sparseness to improve computation efficiency.

Section 10: The BSMGCD Parallel Algorithm
Description 10: Describe the BSMGCD parallel algorithm, including steps for univariate GCD computation, sparse interpolation to recover lost variables, and combining results to obtain the true GCD.

Section 11: Summary and Conclusions
Description 11: Provide a comprehensive summary of key findings, conclusions on the effectiveness of parallel algorithms on SMPs, and insights into performance considerations.

Section 12: Future Work
Description 12: Outline potential areas for future research and development, including further investigations into multivariate polynomial operations, special p-adic lifting techniques, and the use of heterogeneous processor networks for parallel computing in symbolic algebra.