Below is a list of references on the subject of parallel SAC.
%
% REMARKS
% Still under development: inconsistent, incomplete, unchecked, with
% typos, a little mess in general, etc.
%
% HISTORY
% 94-02-22 AN : created (mostly from Kaltofen's & Siegl's bibs).
@Article{ ,
author = "A. Borodin and J. von zur Gathen and J. E. Hopcroft",
title = "Fast parallel matrix and GCD computations",
year = 1982,
journal = "Inf. Control",
volume = 52,
pages = "241--256",
}
@Article{ ,
author = "A. Borodin and S. A. Cook and N. Pippenger",
title = "Parallel computations for well-endowed rings and space-bounded probabilistic machines",
year = 1983,
journal = "Information Control",
volume = 58,
number = 1--3,
pages = "113--136",
}
@Article{ ,
author = "S. A. Cook",
title = "A taxonomy of problems with fast parallel algorithms",
year = 1985,
journal = "Inf. Control",
volume = 64,
pages = "2--22",
}
@Article{ ,
author = "W. Eberly",
title = "Very fast parallel polynomial arithmetic",
year = 1989,
journal = "SIAM J. Comput.",
volume = 18,
number = 5,
pages = "955--976",
}
@Article{ ,
author = "F. E. Fich and M. Tompa",
title = "The parallel complexity of exponentiating polynomials over finite fields",
year = 1988,
journal = "J. ACM",
volume = 35,
number = 3,
pages = "651--667",
}
@Article{ ,
author = "J. von zur Gathen",
title = "Parallel algorithms for algebraic problems",
year = 1984,
journal = "SIAM J. Comp.",
volume = 13,
pages = "802--824",
}
@Article{ ,
author = "J. von zur Gathen",
title = "Representations and parallel computations for rational functions",
year = 1986,
journal = "SIAM J. Comp.",
volume = 15,
pages = "432--452",
}
@Article{ ,
author = "J. von zur Gathen",
title = "Parallel arithmetic computation: A survey",
year = 1986,
journal = "Proc. MFCS '86, Springer Lec. Notes Comp. Sci.",
volume = 233,
pages = "93--112",
}
@Article{ ,
author = "L. Hyafil",
title = "On the parallel evaluation of multivariate polynomials",
year = 1979,
journal = "SIAM J. Comp.",
volume = 8,
pages = "120--123",
}
@Article{ ,
author = "E. Kaltofen",
title = "Fast parallel absolute irreducibility testing",
year = 1985,
journal = "J. Symbolic Comput.",
volume = 1,
pages = "57--67",
}
@Article{ ,
author = "E. Kaltofen and M. S. Krishnamoorthy and B. D. Saunders",
title = "Fast parallel computation of Hermite and Smith forms of polynomial matrices",
year = 1987,
journal = "SIAM J. Alg. Discrete Math.",
volume = 8,
pages = "683--690",
}
@Article{ ,
author = "E. Kaltofen and M. S. Krishnamoorthy and B. D. Saunders",
title = "Fast parallel algorithms for similarity of matrices",
year = 1986,
journal = "Proc. 1986 ACM Symp. Symbolic Algebraic Comp.",
pages = "65--70",
}
@Article{ ,
author = "E. Kaltofen and M. S. Krishnamoorthy and B. D. Saunders",
title = "Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith normal form of polynomial matrices",
year = 1989,
journal = "Proc. EUROCAL '87, Springer Lec. Notes Comput. Sci.",
volume = 378,
pages = "317--322",
}
@Article{ ,
author = "G. L. Miller and V. Ramachandran and E. Kaltofen",
title = "Efficient parallel evaluation of straight-line code and arithmetic circuits",
year = 1988,
journal = "SIAM J. Comput.",
volume = 17,
number = 4,
pages = "687--695",
}
@InProceedings{ ,
author = "G. L. Miller and J. H. Reif",
title = "Parallel tree contraction Part 1: Fundamentals",
year = 1989,
journal = "SIAM J. Comput.",
booktitle = "Randomness in Computation",
editor = "S. Micali",
volume = 5,
pages = "47--72",
institution = "JAI Press Inc.",
}
@Article{ ,
author = "K. Mulmuley",
title = "A fast parallel algorithm to compute the rank of a matrix over an arbitrary field",
year = 1987,
journal = "Combinatorica",
volume = 7,
pages = "101--104",
}
@Article{ ,
author = "L. Valiant and S. Skyum and S. Berkowitz and C. Rackoff",
title = "Fast parallel computation of polynomials using few processors",
year = 1983,
journal = "SIAM J. Comp.",
volume = 12,
pages = "641--644",
}
@Article{ ,
author = "V. Pan and J. Reif",
title = "Efficient parallel solution of linear systems",
year = 1985,
journal = "Proc. 17th ACM Symp. Theory Comp.",
pages = "143--152",
}
@Article{ ,
author = "J. H. Davenport and B. M. Trager",
title = "On the parallel Risch algorithm (II)",
year = 1985,
journal = "ACM Trans. Math. Software",
volume = 11,
pages = "356--362",
}
@Article{ ,
author = "E. Kaltofen and M. S. Krishnamoorthy and B. D. Saunders",
title = "Parallel algorithms for matrix normal forms",
year = 1990,
journal = "Linear Algebra and Applications",
volume = 136,
pages = "189--208",
}
@Article{ ,
author = "D. S. Wise and J. Franco",
title = "Costs of quadtree representation of non-dense matrices",
year = 1990,
journal = "J. Parallel Distributed Comput.",
volume = 9,
pages = "282--296",
}
@Article{ ,
author = "D. Yu. Grigoryev and M. Karpinski and M. F. Singer",
title = "Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields",
year = 1990,
journal = "SIAM J. Comput.",
volume = 19,
number = 6,
pages = "1059--1063",
}
@Article{ ,
author = "R. P. Brent and H. T. Kung",
title = "A regular layout for parallel adders",
year = 1982,
journal = "IEEE Trans. Computers",
volume = {\sc,
number = 3,
pages = "260--264",
}
@InProceedings{ ,
author = "R. M. Karp and V. Ramachandran",
title = "Parallel algorithms for shared-memory machines",
year = 1990,
journal = "IEEE Trans. Computers",
booktitle = "Handbook of Theoretical Computer Science, Algorithms and Complexity (Volume A)",
editor = "J. van Leeuwen",
pages = "869--941",
institution = "Elsevier Science Publ.",
}
@Misc{ ,
author = "T. Leighton and C. E. Leiserson and B. Maggs and S. Plotkin and J. Wein",
title = "Advanced parallel and VLSI computation",
year = 1988,
journal = "IEEE Trans. Computers",
volume = RSS,
institution = "Lab. Comp. Sci., MIT",
}
@Misc{ ,
author = "T. Leighton and C. E. Leiserson and B. Maggs and S. Plotkin and J. Wein",
title = "Theory of parallel and VLSI computation",
year = 1988,
journal = "IEEE Trans. Computers",
volume = RSS,
institution = "Lab. Comp. Sci., MIT",
}
@Article{ ,
author = "R. E. Ladner and M. J. Fischer",
title = "Parallel prefix computation",
year = 1980,
journal = "J. ACM",
volume = 27,
number = 4,
pages = "831--838",
}
@Article{ ,
author = "R. P. Brent",
title = "The parallel evaluation of general arithmetic expressions",
year = 1974,
journal = "J. ACM",
volume = 21,
pages = "201--208",
}
@Article{ ,
author = "U. Vishkin",
title = "Randomized speed-ups in parallel computation",
year = 1984,
journal = "Proc. 16th Annual ACM Symp. Theory Comp.",
pages = "230--239",
}
@Article{ ,
author = "B. E. Litow and G. I. Davida",
title = "O(log(n)) parallel time finite field inversion",
year = 1988,
journal = "Proc. AWOC 88, Springer Lec. Notes Comp. Sci.",
volume = 319,
pages = "74--80",
}
@Article{ ,
author = "R. J. Anderson and G. L. Miller",
title = "Deterministic parallel list ranking",
year = 1988,
journal = "Proc. AWOC 88, Springer Lec. Notes Comp. Sci.",
volume = 319,
pages = "81--90",
}
@Article{ ,
author = "R. Cole and U. Vishkin",
title = "Optimal parallel algorithms for expression tree evaluation and list ranking",
year = 1988,
journal = "Proc. AWOC 88, Springer Lec. Notes Comp. Sci.",
volume = 319,
pages = "91--100",
}
@Article{ ,
author = "S. R. Kosaraju and A. L. Delcher",
title = "Optimal parallel evaluation of tree-structured computations by raking",
year = 1988,
journal = "Proc. AWOC 88, Springer Lec. Notes Comp. Sci.",
volume = 319,
pages = "101--110",
}
@Article{ ,
author = "D. Kozen",
title = "Fast parallel orthogonalization",
year = 1987,
journal = "SIGACT News",
volume = 18,
number = 2,
pages = "47",
}
@Article{ ,
author = "A. L. Chistov",
title = "Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic",
year = 1985,
journal = "Proc. FCT '85, Springer Lec. Notes Comp. Sci.",
volume = 199,
pages = "63--69",
}
@Article{ ,
author = "F. P. Preparata and D. V. Sarwate",
title = "An improved parallel processor bound in fast matrix inversion",
year = 1978,
journal = "Inform. Process. Letters",
volume = 7,
number = 3,
pages = "148--150",
}
@Article{ ,
author = "O. H. Ibarra and S. Moran and L. E. Rosier",
title = "A note on the parallel complexity of computing the rank of order $n$ matrices",
year = 1980,
journal = "Inform. Process. Letters",
volume = 11,
number = 4,5,
pages = "162",
}
@Article{ ,
author = "M. Goldberg and T. H. Spencer",
title = "A new parallel algorithm for the maximal independent set problem",
year = 1989,
journal = "SIAM J. Comput.",
volume = 18,
number = 2,
pages = "419--427",
}
@Article{ ,
author = "M. Goldberg and T. H. Spencer",
title = "Constructing a maximal independent set in parallel",
year = 1989,
journal = "SIAM J. Discr. Math.",
volume = 2,
number = 3,
pages = "322--328",
}
@InProceedings{ ,
author = "D. Eppstein and Z. Galil",
title = "Parallel algorithmic techniques for combinatorial computation",
year = 1988,
journal = "SIAM J. Discr. Math.",
booktitle = "Annual Review in Computer Science",
editor = "J. F. Traub",
volume = 3,
pages = "233--283",
institution = "Annual Reviews Inc.",
}
@InProceedings{ ,
author = "E. Kaltofen and M. F. Singer",
title = "Size efficient parallel algebraic circuits for partial derivatives",
year = 1991,
journal = "SIAM J. Discr. Math.",
booktitle = "IV International Conference on Computer Algebra in Physical Research",
editor = "D. V. Shirkov, V. A. Rostovtsev, and V. P. Gerdt",
pages = "133--145",
institution = "World Scientific Publ.",
}
@Article{ ,
author = "Z. Galil and V. Pan",
title = "Parallel evaluation of the determinant and of the inverse of a matrix",
year = 1989,
journal = "Inform. Process. Letters",
volume = 30,
pages = "41--45",
}
@Article{ ,
author = "L. Csanky",
title = "Fast parallel matrix inversion algorithms",
year = 1976,
journal = "SIAM J. Comput.",
volume = 5,
number = 4,
pages = "618--623",
}
@Article{ ,
author = "S. J. Berkowitz",
title = "On computing the determinant in small parallel time using a small number of processors",
year = 1984,
journal = "Inform. Process. Letters",
volume = 18,
pages = "147--150",
}
@Article{ ,
author = "I. Auger and M. S. Krishnamoorthy",
title = "A parallel algorithm for monadic unification",
year = 1985,
journal = "BIT",
pages = "302--306",
}
@Article{ ,
author = "E. Hvannberg and M. S. Krishnamoorthy",
title = "On transformations in a parallel programming assistant",
year = 1987,
journal = "Proc. MCC-University Research Symposium",
pages = "1--15",
}
@Article{ ,
author = "E. Hvannberg and M. S. Krishnamoorthy",
title = "An object-based parallel programming assistant",
year = 1989,
journal = "SIGPLAN Notices (special issue on Object-Based Concurrent Programming)",
pages = "to",
}
@Misc{ ,
author = "M. S. Krishnamoorthy and D. J. Potter",
title = "Parallel algorithms for the computation of binomial coefficients",
year = 1988,
journal = "SIGPLAN Notices (special issue on Object-Based Concurrent Programming)",
institution = "Dept. Comput. Sci., Rensselaer Polytechnic Institute",
}
@Article{ ,
author = "R. Cole",
title = "Parallel merge sort",
year = 1988,
journal = "SIAM J. Comput.",
volume = 17,
number = 4,
pages = "770--785",
}
@Article{ ,
author = "C. Papadimitriou and M. Yannakakis",
title = "Towards an architecture-independent analysis of parallel algorithms",
year = 1988,
journal = "Proc. 20th Annual ACM Symp. Theory Comp.",
pages = "510--513",
}
@Article{ ,
author = "H. Gazit and G. L. Miller",
title = "A parallel algorithm for finding a separator in planar graphs",
year = 1987,
journal = "Proc. 28th Annual IEEE Symp. Foundations Comput. Sci.",
pages = "238--248",
}
@Misc{ ,
author = "H. Gazit and G. Miller",
title = "A parallel algorithm for bfs of a directed graph",
year = 1987,
journal = "Proc. 28th Annual IEEE Symp. Foundations Comput. Sci.",
}
@Article{ ,
author = "C. Leiserson and B. Maggs",
title = "Communication-efficient parallel graph algorithms",
year = 1988,
journal = "Algorithmica",
volume = 3,
pages = "53--78",
}
@Article{ ,
author = "H. Alt and T. Hagerup and K. Mehlhorn and F. P. Preparata",
title = "Deterministic simulations of idealized parallel computers on more realistic ones",
year = 1986,
journal = "Proc. MFCS '86, Springer Lec. Notes Comp. Sci.",
volume = 233,
pages = "199--208",
}
@Article{ ,
author = "Y. Shiloach and U. Vishkin",
title = "An O(log n) parallel connectivity algorithm",
year = 1982,
journal = "J. of Algorithms",
volume = 3,
pages = "57--67",
}
@Misc{ ,
author = "A. Gibbons and W. Rytter",
title = "Efficient Parallel Algorithms",
year = 1988,
journal = "J. of Algorithms",
institution = "Cambridge Univ. Press",
}
@Misc{ ,
author = "E. Kaltofen",
title = "Processor efficient parallel computation of polynomial greatest common divisors",
year = August~1989,
journal = "J. of Algorithms",
institution = "Dept. Comput. Sci., Rensselaer Polytechnic Institute",
}
@Article{ ,
author = "N. Shankar and V. Ramachandran",
title = "Efficient parallel circuits and algorithms for division",
year = 1988,
journal = "Information Process. Letters",
volume = 29,
pages = "307--313",
}
@Article{ ,
author = "F. Annexstein and M. Baumslag and A. L. Rosenberg",
title = "Group action graphs and parallel architectures",
year = 1990,
journal = "SIAM J. Comput.",
volume = 19,
number = 3,
pages = "544--569",
}
@Article{ ,
author = "R. Cole and U. Vishkin",
title = "Deterministic coin tossing with applications to optimal parallel list ranking",
year = 1986,
journal = "Information and Control",
volume = 70,
pages = "32--53",
}
@Article{ ,
author = "B. D. Saunders and H. R. Lee and S. K. Abdali",
title = "A parallel implementation of the cylindrical algebraic decomposition algorithm",
year = 1989,
journal = "Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput.",
pages = "298--307",
institution = "ACM Press",
}
@Misc{ ,
author = "S. M. Watt",
title = "Bounded Parallelism in Computer Algebra",
year = 1986,
journal = "Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput.",
institution = "Dept. Comput. Sci., Univ. Waterloo",
}
@Article{ ,
author = "L. G. Valiant and S. Skyum",
title = "Fast parallel computation of polynomials using few processors",
year = 1981,
journal = "Proc. ICALP 81, Springer Lect. Notes Comput. Sci.",
volume = 118,
pages = "132--139",
}
@Article{ ,
author = "V. Ramachandran and J. Reif",
title = "On optimal parallel algorithm for graph planarity",
year = 1989,
journal = "Proc. 30th Annual Symp. Foundations of Comp. Sci.",
pages = "282--287",
institution = "IEEE",
}
@Article{ ,
author = "M. J. Atallah and S. R. Kosaraju and L. L. Larmore and G. L. Miller and S.-H. Teng",
title = "Constructing trees in parallel",
year = 1989,
journal = "Proc. 1989 ACM Symp. Parallel Algorithms and Architectures",
pages = "421--431",
institution = "ACM Press",
}
@InProceedings{ ,
author = "W. Neun and H. Melenk",
title = "Very large Gr\"obner basis calculations",
year = 1992,
journal = "Proc. 1989 ACM Symp. Parallel Algorithms and Architectures",
booktitle = "Computer Algebra and Parallelism",
volume = 584,
pages = "89--99",
institution = "Springer Verlag",
}
@InProceedings{ ,
author = "E. Kaltofen",
title = "Dynamic parallel evaluation of computation DAGs",
year = 1993,
journal = "Proc. 1989 ACM Symp. Parallel Algorithms and Architectures",
booktitle = "Synthesis of Parallel Algorithms",
editor = "J. Reif",
pages = "723--758",
institution = "Morgan Kaufmann Publ.",
}
@InProceedings{ ,
author = "B. W. Char",
title = "Progress report on a system for general-purpose parallel symbolic algebraic computation",
year = 1990,
journal = "Proc. 1989 ACM Symp. Parallel Algorithms and Architectures",
booktitle = "Proc. 1990 Internat. Symp. Symbolic Algebraic Comput.",
editor = "S. Watanabe and M. Nagata",
pages = "96--103",
institution = "ACM Press",
}
@Misc{ ,
author = "J.-L. Roch",
title = "Calcul Formel et Parall\'elism",
year = 1989,
journal = "Proc. 1989 ACM Symp. Parallel Algorithms and Architectures",
institution = "Inst. National Polytechnique",
}
@Article{ ,
author = "K. Abrahamson and N. Dadoun and D. G. Kirkpatrick and T. Przytycka",
title = "A simple parallel tree contraction algorithm",
year = 1989,
journal = "J. Algorithms",
volume = 10,
pages = "287--302",
}
@InProceedings{ ,
author = "S. Seitz",
title = "Algebraic computing on a local net",
year = 1992,
journal = "J. Algorithms",
booktitle = "Computer Algebra and Parallelism",
volume = 584,
pages = "19--31",
institution = "Springer Verlag",
}
@Article{ ,
author = "R. D. Silverman and S. J. Stuart",
title = "A distributed batching system for parallel processing",
year = 1989,
journal = "Software---Practice Experience",
volume = 19,
number = 12,
pages = "1163--1174",
}
@Article{ ,
author = "V. Pan",
title = "Parallel least-square solution of general and Toeplitz-like linear systems",
year = 1990,
journal = "Proc. 2nd Ann. Symp. Parallel Algorithms Architecture",
pages = "244-253",
institution = "ACM Press",
}
@InProceedings{ ,
author = "M. Sullivan and D. Anderson",
title = "Marionette: a system for parallel distributed programming using a master/slave model",
year = 1989,
journal = "Proc. 2nd Ann. Symp. Parallel Algorithms Architecture",
booktitle = "Proc. 9th Internat. Conf. Distr. Comput. Syst.",
pages = "181--188",
institution = "IEEE",
}
@Article{ ,
author = "V. Pan",
title = "Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros",
year = 1989,
journal = "Computers Math. Applic.",
volume = 17,
number = 11,
pages = "1475--1480",
}
@InProceedings{ ,
author = "S. R. Kosaraju",
title = "On the parallel evaluation of classes of circuits",
year = 1990,
journal = "Computers Math. Applic.",
booktitle = "Foundations of Software Technology and Theoretical Computer Science",
editor = "Nori, K. V. and Veni Madhavan, C. E.",
volume = 472,
pages = "232--237",
}
@InProceedings{ ,
author = "E. Kaltofen and V. Pan",
title = "Processor efficient parallel solution of linear systems over an abstract field",
year = 1991,
journal = "Computers Math. Applic.",
booktitle = "Proc. 3rd Ann. ACM Symp. Parallel Algor. Architecture",
pages = "180--191",
institution = "ACM Press",
}
@Misc{ ,
author = "F. T. Leighton",
title = "Introduction to Parallel Algorithms and Architectures: Arrays, Trees \& Hypercubes",
year = 1991,
journal = "Computers Math. Applic.",
institution = "Morgan Kaufmann Publ.",
}
@Article{ ,
author = "J. Chun and T. Kailath and H. Lev-Ari",
title = "Fast parallel algorithms for QR and triangular factorizations",
year = 1987,
journal = "SIAM J. Sci. Stat. Comput.",
volume = 8,
number = 6,
pages = "899--913",
}
@InProceedings{ ,
author = "D. Bini and L. Gemignani and V. Pan",
title = "Improved parallel computations with matrices and polynomials",
year = 1991,
journal = "SIAM J. Sci. Stat. Comput.",
booktitle = "Proc. ICALP 91",
editor = "J. Leach Albert, B. Monien, and E. Rodr\'\i guez Artalejo",
volume = 510,
pages = "520--531",
}
@InProceedings{ ,
author = "P. S. Wang",
title = "Parallel univariate polynomial factorization on shared-memory multiprocessors",
year = 1990,
journal = "SIAM J. Sci. Stat. Comput.",
booktitle = "Proc. 1990 Internat. Symp. Symbolic Algebraic Comput.",
editor = "S. Watanabe and M. Nagata",
pages = "145--151",
institution = "ACM Press",
}
@Article{ ,
author = "M. Ben-Or and E. Feig and D. Kozen and P. Tiwari",
title = "A fast parallel algorithm for determining all roots of a polynomial with real roots",
year = 1988,
journal = "SIAM J. Comput.",
volume = 17,
number = 6,
pages = "1081--1092",
}
@Misc{ ,
author = "D. A. Linwood",
title = "Roots of a polynomial via a parallel Newton's method",
year = 1990,
journal = "SIAM J. Comput.",
institution = "Dept. Math., California State University",
}
@InProceedings{ ,
author = "E. Kaltofen",
title = "Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems",
year = 1993,
journal = "SIAM J. Comput.",
booktitle = "Proc. AAECC-10",
editor = "G. Cohen, T. Mora, and O. Moreno",
volume = 673,
pages = "195--212",
}
@Misc{ ,
author = "R. E. Zippel~(Ed.)",
title = "Proc. 2nd Internat. Workshop on Computer Algebra and Parallelism",
year = 1992,
journal = "SIAM J. Comput.",
volume = 584,
}
@Article{ ,
author = "E. Kaltofen and V. Pan",
title = "Processor-efficient parallel solution of linear systems II: the positive characteristic and singular cases",
year = 1992,
journal = "Proc. 33rd Annual Symp. Foundations of Comp. Sci.",
pages = "714--723",
institution = "IEEE Computer Society Press",
}
@InProceedings{ ,
author = "W. Eberly",
title = "Efficient parallel independent subsets and matrix factorizations",
year = 1991,
journal = "Proc. 33rd Annual Symp. Foundations of Comp. Sci.",
booktitle = "Proc. 3rd IEEE Symp. Parallel Distr. Processing",
pages = "204--211",
institution = "IEEE",
}
@Article{ ,
author = "L. G. Valiant",
title = "A bridging model for parallel computation",
year = 1990,
journal = "Commun. ACM",
volume = 33,
number = 8,
pages = "103--111",
}
@InProceedings{ ,
author = "H. Hong and W. Schreiner",
title = "A new library for parallel algebraic computation",
year = 1993,
journal = "Commun. ACM",
booktitle = "Sixth SIAM Conference on Parallel Processing for Scientific Computing, vol. 2",
editor = "Sincovec, R. F., et \al{}",
pages = "776--783",
institution = "SIAM",
}
@Article{ ,
author = "C. H. Huang",
title = "A fully parallel mixed-radix conversion algorithm for residue number applications",
year = 1983,
journal = "IEEE Trans. Comput.",
volume = {\sc,
pages = "398--402",
}
@Article{ ,
author = "G. I. Davida and B. Litow",
title = "Fast parallel arithmetic via modular representation",
year = 1991,
journal = "SIAM J. Comput.",
volume = 20,
pages = "756--765",
}
@InProceedings{ ,
author = "J. Cheriyan and J. H. Reif",
title = "Parallel and output sensitive algorithms for combinatorial and linear algebra problems",
year = 1993,
journal = "SIAM J. Comput.",
booktitle = "Proc. 5th Ann. ACM Symp. Parallel Algor. Architecture",
pages = "to",
institution = "ACM Press",
}
@Misc{ ,
author = "E. J. Schwabe and G. E. Blelloch and A. Feldmann and O. Ghattas and J. R. Gilbert and G. L. Miller and D. R. O'Hallaron and J. R. Shewchuk and S.-H. Teng",
title = "A separator-based framework for automated partitioning and mapping of parallel algorithms for numerical solution of PDEs",
year = 1993,
journal = "SIAM J. Comput.",
pages = "15",
institution = "Carnegie Mellon Univ.",
}
@Misc{ ,
author = "J. J\'aJ\'a",
title = "An Introduction to Parallel Algorithms",
year = 1992,
journal = "SIAM J. Comput.",
institution = "Addison_Wesley Publ. Comp.",
}
@Article{ ,
author = "E. Kaltofen",
title = "Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems",
year = ,
journal = "Math. Comput.",
pages = "to",
}
@Misc{,
author = "Winfried Neun",
title = "Using PVM based software for Parallel Computation in Computer Algebra",
howpublished = "Rhine Workshop 1994 (to appear)",
year = "1994",
}
@TechReport{ Batey:92,
Author = "Batey, D.J.",
Title = "{DPL}---{A} {D}istributed {I}mplementation of {P}aralation {L}isp",
institution = "University of Bath Computing Group",
Year = 1992,
month = "June",
number = "92--60"
}
@inproceedings{ Batey_Padget:93,
Author = "Batey, D.J. and Padget, J.A.",
Title = "{T}owards {A} {V}irtual {M}ulticomputer",
Booktitle = "Proc. of Workshop on Heterogeneous Processing at
the 7th International Parallel Processing Symposium",
Publisher = "IEEE Computer Society",
Address = "University of Southern California, Newport Beach,
CA",
Year = 1993,
Pages = "71--76",
Month = "April"
}
@Article{ Berrington_Broadbery_DeRoure_Padget:93,
author = "Berrington, N. and Broadbery, P.A. and DeRoure, D.C.
and Padget, J.A.",
title = "{EuLisp Threads: A Concurrency Toolbox}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "177--200",
}
@Article{ Berrington_DeRoure_Padget:93,
author = "Berrington, N. and {DeRoure}, D.C. and Padget, J.A.",
title = "{G}uaranteeing {U}npredictability",
journal = "The Computer Journal",
year = "1993",
volume = "36",
number = "8",
month = "December",
pages = "723--733"
}
@Article{ Bradford_DeRoure:93,
author = "Bradford, R.J. and DeRoure, D.C.",
title = "{EuLisp in Education}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "99--118",
}
@inproceedings{ Bretthauer_Davis_Kopp_Playford:92,
author = "{Bretthauer, H.} and {Davis, H.E.} and {Kopp, J.} and
{Playford, K.J.}",
title = "{B}alancing the {EuLisp} {M}etaobject {P}rotocol",
booktitle = "Proc. of International Workshop on New Models for
Software Architecture",
year = 1992,
month = "Nov",
address = "Tokyo, Japan"
}
@Article{ Bretthauer_Kopp_Davis_Playford:93,
author = "Bretthauer, H. and Kopp, J. and Davis, H.E. and
Playford, K.J.",
title = "{Balancing the EuLisp Metaobject Protocol}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "119--138",
}
@Article{ Broadbery_Burdorf:93,
author = "Broadbery, P.A. and Burdorf, C.",
title = "{Applications of Telos}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "139--158",
}
@InProceedings{ Burdorf:92,
author = "Burdorf, C.",
title = "{POCONS}: {A} {P}ersistent {O}bject-based {C}onnectionist {S}imulator",
series = "Proceedings of the 1992 SCS Western Multiconference:
Object-Oriented Simulation",
year = "1992",
organization = "Society for Computer Simulation"
}
@PhdThesis{ Burdorf:93,
author = "Burdorf, C.",
title = "{P}arallel {P}ersistent {O}bject-{O}riented
{S}imulation with {A}pplications",
school = "University of Bath",
year = "1993"
}
@inproceedings{ Collins_Johnson_Kuechlin:90,
author = {Collins, George E. and Johnson, Jeremy R. and K{\"u}chlin, Wolfgang },
title = {{Parallel Real Root Isolation Using the Coefficient Sign Variation Method}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {71--87},
abstract={
We present a parallel implementation of the coefficient sign variation method for polynomial
real root isolation. The implementation uses PARSAC-2, a parallel version, based on threads,
of the SAC-2 computer algebra system. A discussion of the implementation and its performance
is given. Our timing results where obtained on a shared memory multiprocessor implementation
using the Encore Multimax.
}
}
@proceedings{ Dora_Fitch:89,
title = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
}
@inproceedings{ Fitch:89,
author = {Fitch, John},
title = {{Compiling for Parallelism}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {19--31},
abstract = {
There are many ways in which it is possible to start the quest for
parallelism in an algebra system. The work described here is based on a
small number of clear criteria which have shaped the whole project. The first
section of the paper presents these and gives the justification for them.
The details of the compilation for parallelism form the subject of the second
section. There are a number of basic enabling technologies on which our work
is based, and these are explained here. the third part of the paper describes
briefly the multiprocessor LISP system we have constructed. The paper finishes
with some assessment of how far we have got, and some speculation on the future
of the project.
}
}
@inproceedings{ Goldman_Hulzen:89,
author = {Goldman, V.V and Hulzen, J.A.},
title = {{Automatic Code Vectorization of Arithmetic Expressions by Bottom-Up
Structure Recognition}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {119--132},
abstract={
A bottom-up structure recognizer for vectorizing or parallelizing
scalar code typicaly generated by computer algebra processing is
proposed. A small example is worked out and some importaint
issues are discussed.
}
}
@Article{ Kind_Friedrich:93,
author = "Kind, A. and Friedrich, H.",
title = "{A Practical Approach to Type Inference for EuLisp}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "159--176",
}
@inproceedings{ Kuechlin:90,
author = {K{\"u}chlin, Wolfgang},
title = {{The S-Threads Environment for Parallel Symbolic Computation}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {1--18},
abstract= {
This paper presents a programming environment, based on {\em threads of control}, that is
suitable for parallel {\em symbolic} computation on shared memory multiprocessors. The
S-threads system offers a solution to the problem of whether to have heap memory shared
and global, or distributed, and local to threads. The memory structure makes it particularly
easy to reclaim, without garbage collection, all intermediate list memory used by an algorithm;
under some additional resstrictions, S-threads may alpso perform independent garbage collections.
The S-threads environment is being used in the construction of the PARSAC system, a parallel
version of the SAC-2 Computer Algebnra System. To dat, in Summer 1990, PARSAC-2.1 contains
parallel algorithms for integer multiplication and for isolating the real roots of integer polynomials
work on parallel multivariate polynomial g.c.d. calculation and on parallel root isolation of
algebraic polynomials is under way. S-threads and PARSAC-2 are implemented on an Encore
Multimax, based on the C Threads environment emulated by Encore Parallel Threads.
}
}
@Article{Kuechlin:92,
author = {K{\"u}chlin W.},
title = {The Multi-Threaded Computation of Modular
Polynomial Greatest Common Divisors},
journal = LNCS,
year = 1992,
volume = 591,
pages = {369--384},
}
@Article{Li_Li_Liu:93,
author = {La Li and Hl Li and Yx Liu:93},
title = {A Decision Algorithm for Linear Sentences on a PFM},
journal = {Annals of Pure and Applied Mathematics},
year = 1993,
volume = 59,
number = 3,
pages = {273--286}
}
@inproceedings{ Melenk_Neun:89,
author = {Melenk, Herbert and Neun, Winfried},
title = {{Implementation of the LISP-Arbitrary Precision Arithmetic for
a Vector Processor}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {76--89},
abstract = {
Portable Standard LISP (PSL, Version 3.4) and REDUCE 3 where implemented for
CRAY 1 and CRAY X-MP computers at the Konrad-Zuse-Zentrum f{\"u}r
Informationstechnik Berlin in 1986. As an special aspect of the implementation
of PSL, an interface to the vector hardware of CRAY processors was defined. With
that interface and mostly driven by the needs of REDUCE applications (e.g.
extensive calculations of Gr{\"o}bner bases), the arbitrary precision integer
arithmetic of PSL was rebuild using full power of vector hardware. A modular
arithmetic using vector hardware was also constructed.
}
}
@inproceedings{ Melenk_Neun:89,
author = {Melenk, Herbert and Neun, Winfried},
title = {{Parallel Polynomial Operations in the Large Buchberger Algorithm}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {143--158},
abstract = {
The Buchberger algorithm for the construction of a Gr{\"o}bner base from a given
set of polynomials is an example for the claculation with polynomials in distributive
representation. It is shown, that the algorithm can be based on one single polynomial
operation, a ``linear combination''. This operation can be rewritten as a merge operation
such that the arising result can become input for a subsequent processing step as soon
as the first monomial is ``readdy''. This property is the source for parallel execution,
which technically is supported by an objectoriented programming approach and by a process model.
}
}
@inproceedings{ Melenk_Neun:90,
author = {Melenk, Herbert and Neun, Winfried},
title = {{Very Large Gr{\"o}bner Basis Calculations}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {90--99},
abstract={
The attempt to solve systems of polynomial equations with Gr{\"o}bner base techniques
often leads to large problems which exceed the available computer resources with their
requirements of cpu time or storage. The well-known reason for that is the swell of intermediate
polynomials, which are generated during the basis calculation and which are in most cases
not included in either the given set of polynomials or the resulting Gr{\"o}bner basis. In this
paper two different approaches to overcome the problem are presented which benefit from the
usage of parallel computers, namely the vectorization of the arbitrary precision integer
arithmetic and the useage of decomposition techniques. Especially the decomposition approach,
where applicable leads to massive parallelism in the problem solution, which results in a
breakthrough for several problems.
}
}
@InProceedings{ Merrall_Padget:92,
Author = "Merrall, S.C. and Padget, J. A.",
Title = "Collections and Garbage Collection",
Editor = "Lang, B.",
number = "637",
series = "LNCS",
pages = "473--489",
booktitle = "Proc. of International Workshop on Memory Management",
Year = 1992,
publisher = "Springer Verlag"
}
@Article{ Merrall_Padget:93,
author = "Merrall, S. and Padget, J.A.",
title = "{Plurals: A SIMD Extension to EuLisp}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
OPTpages = "201--219",
}
@PhdThesis{ Odeh:93,
author = "Odeh, M.H.",
title = "{C}oncurrent {O}bject-oriented {E}xecution of {OPS5}
{P}roduction {S}ystems",
school = "University of Bath",
year = "1993"
}
@InProceedings{ Odeh_Padget:93,
author = "Odeh, M.H. and Padget, J.A.",
title = "{O}bject-oriented {E}xecution of {OPS5} {P}roduction
{S}ystems",
OPTpages = "",
booktitle = "OOPSLA '93",
year = "1993",
organization = "ACM",
publisher = "ACM Press"
}
@Article{ Padget:91,
author = "Padget, J.A. and Bradford, R.J. and Fitch, J.P.",
title = "{C}oncurrent {O}bject-{O}riented {P}rocessing in {Lisp}",
journal = "Computer Journal",
year = "1991",
volume = "34",
number = "4",
pages = "311--319",
month = "August"
}
@InProceedings{ Padget_Batey_Merrall:93,
author = "Padget, J.A. and Batey, D.J. and Merrall, S.",
title = "Architecture Independence and Coordination",
editor = "Halstead, R.H.Jr. and Ito, T.",
number = "748",
series = "LNCS",
OPTpages = "",
booktitle = "Parallel Symbolic Computing: Languages, Systems, and
Applications (US/Japan Workshop Proceedings)",
year = "1993",
publisher = "Springer Verlag",
note = "in press"
}
@Misc{ Padget_Nuyens:94,
author = "Padget, J.A. and Nuyens, G. (editors)",
title = "{T}he {EuLisp} {D}efinition (version 0.99)",
howpublished = "Available from University of Bath ({\tt
ftp.bath.ac.uk} in directory {\tt /pub/eulisp}",
year = "1994"
}
@Article{ Padget_Nuyens_Bretthauer:93
author = "Padget, J.A. and Nuyens, G. and Bretthauer, H.",
title = "{An overview of EuLisp}",
journal = "Lisp and Symbolic Computation",
year = "1993",
volume = "6",
number = "1/2",
pages = "9--98",
}
@inproceedings{ Roch:89,
author = {Roch, J. L.},
title = {{PAC: Towards a parallel computer algebra co-processor}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {33--50},
abstract = {
PAC is a computer algebra system, based on MIMD type parallelism.
It uses parallelism as a tool for processing problems which are too complex
for sequential treatment. Basic fundamentals of the system are firstly
discussed. Then, the implementation of infinite-precision arithmetic with
vectors is detailed (addition, substraction, multiplication, division in
$\cal Q$, gcd and Bezout algorithm in $\cal Z$).
PAC is implemented on the Floating Point System hypercube:
Tesseract 20 (16 nodes). To increase the speed of basic routines,
some modules have been rewritten in assembly languages for Inmos T414
transputer. Different experiments have been done to compare PAC performances (for basic arithmetic) to Maclisp.
}
}
@inproceedings{ Roch:90,
author = {Roch, J. L.},
title = {{An environment for parallel algebraic computation}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {33--50},
abstract={
PAC is a parallel environment, based on a MIMDdistributed computing model, which is
intended to aid in the development of computer algebra algorithms. It uses parallelism as a
tool for processing large problems. This paper discusses a general relationship between
computer algebra and parallelism. The gheneral features of the PAC project are described and
some of the results obtained with PAC are presented. One of the crucial elements of symbolic
computation on parallel architectures is efficient implementation of fast arbitrary precision
arithmetic. This paper presents a nodal (arbitrary precision) integer arithmetic package and
discusses the fast division algorithm which we have implemented. The representation used
is designed to take advantage of a vectorized floating point unit. Our experiences with this
approach are discussed.
PAC has been implemented on the FPS T series hypercube (32 processors) and an
implementation on the TELMAT Meganode (128 processors) is in progress.
}
}
@Article{Roch_Vermeerb_Villard:92,
author = {J.L. Roch and A. Vermeerb and G. Villard},
title = {Cost Prediction for Load-Balancing - Applications to Algebraic Computation},
journal = LNCS,
year = 1992,
volume = 634,
pages = {467--478}
}
@Article{Roch_Villard:92,
author = {J.L. Roch and G. Villard},
title = {Parallel GCD and Lattice Basis Reduction},
journal = LNCS,
year = 1992,
volume = 634,
pages = {557--564}
}
@inproceedings{ Seitz:89,
author = {Seitz, Steffen},
title = {{Parallel Algorithm Development}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {223 --232},
abstract= {
Using the SAC-2 computer algebra system on a network of SUN Workstations, we show
how the user can utilize severalmachines for the execution of a program simply by setting
the unit number for input and output. Our approach is demonstrated by a distributed
version of the algorithm IPRES from the GCD and Resultant Package of the SAC-2 library.
}
}
@inproceedings{ Seitz:90,
author = {Seitz, Steffen},
title = {{Algebraic Compoutation on a Local Net}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {19--31},
abstract= {
An extension of the computer algebra system SAC-2 for the execution of algorithms by the
workstations on a local net is described. We are more interested in the reduction of the execution
time of existing algorithms than in the development of new parallel computing models. The
semantics of the SAC-2 system language ALDES is extended for the specification of concurrent
procedure calls. During the parallel execution of these calls the results are represented by futures,
whose existence is hidden to the programmer by using data types. the current implementation, based
on the SAC-2 I/O concept, is described. As an example for algorithmss with many concurrent
subtasks, the execution times for a distributed version of a modular algorithm are shown.
}
}
@inproceedings{ Senechaud:89,
author = {Senechaud, Pascale},
title = {{Implementation of a parallel algorithm to compute a Gr{\"o}bner basis
on boolean polynomials}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {159--166},
abstract = {
Gr{\"o}bner bases are an importaint methematical tool which has applications in geometry
and algebra. Some sequential algorithms to compute a Gr{\"o}bner basis have been
implemented in most of the computer algebra systems (Macsyma, ScratchpadII) and also on
Macintosh in C. A parallelization of these algorithms, interesting because of the data size,
has only been studied with different machine model from this presented here.
We study boolean polynomials for which the construction of Gr{\"o}bner bases is more simple.
The generalization does not modify the parallel algorithm structure: Only the basic
operations and the data structure are different.
Boolean Gr{\"o}bner bases have applications in logic.
}
}
@inproceedings{ Senechaud:90,
author = {Senechaud, Pascale},
title = {{Boolean Gr{\"o}bner Basis and Their MIMD Implementation}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {101--114},
abstract={
We present two methods to compute Gr{\"o}bner bases in parallel, both based on
Buchberger's sequential algorithm. A distributed memory MIMD computer (the FPS 140)
gives experimental results optained with boolean polynomials.
The algorithms where implemented on the FPS T40 connected as a ring and as a
hypercube of processors. The first implementation shows the interest of the parallelization.
The second one, based on a divide and conquer strategy, has a behavior very close to
to the squential algorithm.
We evaluate the contribution of parallelism by a direct comparison of sequential
and parallel times without references to complexity.
}
}
@inproceedings{ Siebert-Roch:89,
author = {Siebert-Roch, Francoise},
title = {{Solving Linear Diophantine equation in parallel}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {207 -- 222},
abstract = {
Find out the Hermite normal form of a matrix A is a way to solve the system $A x = b$
for integral value of $x$, where $A$ is an integral matrix and $b$ an integral column
vector.
Solving integral linear systems in Computer Algebra requires to handle a large number
of integers and the algorithms show some importaint intermediate coefficient swell. These
factors have lead us to consider a parallel implementation.
This paper is dedicated to a particular problem: solving a linear Diophantine equation.
In the first part we give a brief theoretical overview of that subject. Then we present an
algorithm described by W.A. Blankinship determining the GCD $d$ of $n$ positive integers
$a_1, a_2, ..., a_n$ and giving a solution $x_1, x_2, ..., x_n$ for the Diophantine equation:
$$ d=a_1 x_1 + a_2 x_2 + ... + a_n x_n. $$
This algorithm has been parallelized and implemented on a parallel machine of MIMD type.
Some experimental results are presented in the last part of the paper. This work is a first
step in the parallelization study of algorithms as Hermite, Lenstra, ... .
}
}
@inproceedings{Siebert_Mattson_Jackson:90,
author = {Sibert, Ernest and Mattson, Harold F. and Jackson, Paul},
title = {{Finite Field Arithmetic Using the Connection Machine}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {51--61},
abstract={
A Connection Machine (model CM-2) with 32K processors has been used to carry out
calculations inn finite fields with as many as $2^21$ elements and of various characteristics;
a typical calculation is to determine the nuber of roots of a large family of polynomials.
The programs use discrete logarithms, employing a table of ``successor'' logarithms to
perform addition. The table is computed in advance, in parallel. The system can evaluate
some $4 \times 10^6$ polynomial terms per second; performance is limited by the general
communication time needed for table lookup. Orbits of the $p$-th power bijection (also
calculated in parallel) are used to deal with common symmetries arising in the calculations.
The techniques are illustrated by calculations to determine the number of rational points
of a polynomial surface over several fields, quantities which are useful in analyzing certain
cyclic codes.
}
}
@inproceedings{ Tan_Wang:89,
author = {Tan, Trevor B. and Wang, Paul S.},
title = {{Automatic Generation of Parallel Code for the Warp Computer}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {91--117},
abstract = {
GENW2 is a parallel code generator written in Franz Lisp that runs under the
Vaxima symbolic computation system. Given high-level algorithm specifications
and symbolic expressions in list representations, GENW2 outputs W2 code for the
Warp systolic array computer. GENW2 supports three high-level parallel
programming paradigms: pipelining, multitasking and array processing. Parallel
algorithms specified in these paradigms are automatically mapped onto the Warp
architecture freeing the user from much details of interprocess comunication
and synchronization. A code template can be specified by the user to render the
output code in a designated format. Generated routines may involve declarations,
I/O statements, flow control, data distribution, subroutines, functions and
macros. Large expressions are automatically segmented to smaller pieces. An
optional code optimization phase is available. The development of GENW2 is
motivated by research in automatic derivation and generation of parallel code
for finite element analysis. however the package can be used independently.
}
}
@inproceedings{ Villard:89,
author = {Villard, Gilles},
title = {{Exact parallel solution of linear systems}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {197 --205},
abstract = {
A lot of algorithms provide the exact integer or rational solution of a linear system.
Solution may evidently be obtained by a direct computation; an alternative to reduce
the {\em intermediary coefficients swell} is to use reductions modulo primes and
p-adic expansions. We present here the parallel implementations which permit us
to compare the two methods when applied to large systems.
}
}
@inproceedings{ Weeks:89,
author = {Weeks, Dennis},
title = {{Adaption of SAC-1 algorithms for an SIMD machine}},
booktitle = {{Computer algebra and parallelism}},
editor = {Della Dora and Fitch},
publisher = {Academic Press},
year = {1989},
pages = {167 --177},
abstract = {
The list processing and multi-precision integer arithmetic procedures of the
SAC-1 software package have been adapted for use on the Convex C-series,
a family of ``minisupercomputers'' with Cray-like vector registers. A 45:1
speedup was optained on a specific test case of Buchberger's Gr{\"o}bner
basis algorithm by ``tuning'' the SAC-1 routines for the Convex vector
architecture. Although the vector architecture was motivation for the changes,
a close analysis reveals that a significant part of the improved performance
was due to generic changes in the listprocessing algorithms which would be
applicable to almost any computer, and another major improvement was due
to the Convex computer's ability to do 64-bit integer arithmetic.
}
}
@inproceedings{ Weeks:90,
author = {Weeks, Dennis},
title = {{Embarrassingly Parallel Algorithms for Algebraic Number Arithmetic -- and some
less trivial issues}},
booktitle = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
pages = {63--70},
abstract={
Representing algebraic numbers $\alpha$ and $\beta$ by their defining polynomials
is an alternative to the older representation in which the sum $\alpha + \beta$ would be
represented by a list of character strings recursively involving root indices, +, -, $\times$, /,
and integer terms or radicands. Algorithms for sums, products, etc., in the defining
polynomial representation, are based on the theory of symetric functions and have relatively
efficient implementations using polynomial resultants. Even better algorithms use power sums
rather than the coefficients of the defining polynomials; on massively parallel systems
$\alpha \times \beta$ executes in constant time, and computation of $\alpha + \beta$ is linear
(or logarithmic, if enough processors are available) in $m n$, where $m$ and $n$ are degrees
of the defining polynomials and $m n$ is the degree of the result. However, given polynomials
of degree $m$ and $n$, these algorithms require their power sums to order $m n$. The best
known power-sum algorithm is based on Newton's identity, which may be treated as a linear
recurrence, whose solution, conventionally understood to be of complexity $O(mn)$, will
dominate the time of the multiplication algorithm and significantly increase the addition time.
A parallel algorithm, reducing the recurrence solution to $O((log_2 n)(log_2 m)), is discussed.
}
}
@proceedings{ Zippel:90,
title = {{Computer algebra and parallelism, Proceedings of the
second International Workshop on Parallel Algebraic Computation}},
editor = {Zippel},
address = {Ithaca, USA, May},
year = {1990},
publisher = {LNCS 584, Springer Verlag},
}
@phdthesis{ kweber-thesis,
author = "Kenneth Weber",
title =
"Parallel Integer GCD Algorithms and Their Application to Polynomial GCD",
school = "Kent State University",
year = 1994
}
@article { weber,
author = "Ken Weber",
title = "The Accelerated Integer GCD Algorithm",
journal = TOMS,
year = 1994,
note = "to appear"
}