Parallel algorithms for algebraic problems
Parallel algorithms for algebraic problems
复制标题
DOI：
10.1145/800061.808728
复制
发表时间：
1983-12
期刊：
影响因子：
--
通讯作者：
J. Gathen
中科院分区：
文献类型：
--
作者：
J. Gathen
在Borodin-von Zur Gaten-Hopcroft[82]中，编制了以下程序：获得“并行代数计算的理论包”，即对在代数环境中广泛使用的符号处理问题进行快速并行计算。本文考虑了两个基本问题：求解线性方程组和计算任意基场上两个多项式的广义扩散函数。本文继续这一程序，给出了下列代数问题的快速并行解：计算任意域上两个多项式的扩展欧几里德格式的所有项，多个多项式的GCD和LCM，有限域上的因式分解，以及特征零域和有限域上多项式的无平方分解。
In Borodin-von zur Gathen-Hopcroft[82] the following program is laid out: obtain a “theory package for parallel algebraic computations”, i.e. fast parallel computations for the widely used problems of symbolic manipulation in an algebraic context. In that paper, two basic problems were considered: solving systems of linear equations and computing the gcd of two polynomials, both over arbitrary ground fields. The present paper continues this program, and fast parallel solutions to the following algebraic problems are given: computing all entries of the Extended Euclidean Scheme of two polynomials over an arbitrary field, gcd and lcm of many polynomials, factoring polynomials over finite fields, and the squarefree decomposition of polynomials over fields of characteristic zero and over finite fields.