Computer algebra on MIMD machine

ABSTRACT

PAC is a computer algebra system, based on MIMD type parallelism. It uses parallelism as a tool for processing problems wich are too complex for a sequential treatment. Basic fundamentals of the system are firstly discussed. Then, different problems are studied, particularly the implementation of infinite-precision arithmetic, the solution of linear systems and of Diophantine equations, the parallelization of Buchberger's algorithm for Gröbner bases.A prototype of PAC is implemented on the Floating Point System hypercube Tesseract 20 (16 nodes), and different timing results obtained on this machine are given.

REFERENCES

• 1: Harold Abelson , Gerald Jay Sussman , Julie Sussman, Structure and interpretation of computer programs, MIT Press, Cambridge, MA, 1985
• 2: A. V. Aho, J. E. Hopcroft, J. D. Ullman "Data Structure & Algorithm" (p. 378--407) Addison-Wesley (1983).
• 3: E. H. Bareiss, "Computational Solution of Matrix Problems over an Integral Domain", J. Inst. Math. Applic. 10 (1972), 68--104.
• 4: D. Bayer and M. Stillman "The Design of Macaulay: A System for Computing in Algebraïc Geometry and Commutative Algebra." (January 1986).
• 5: W. A. Blankinship, A new version of the Euclidean algorithm, Amer. Math. Monthly, vol. 70, No. 3, (1967).
• 6: Bruno Buchberger, A critical-pair/completion algorithm for finitely generated ideals in rings, Proceedings of the Symposium "Rekursive Kombinatorik" on Logic and Machines: Decision Problems and Complexity, p.137-161, May 23-28, 1983
• 7: B. Buchberger. "Basic Features and Developpment of the Critical Pair / Completion Procedure". Preprint J. Kepler University Austria
• 8: S. Cabay , T. P. L. Lam, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.386-397, Dec. 1977 [doi>10.1145/355759.355765]
• 9: J. Chazarain. "The Lady, the tiger and the Gröbner Basis". Preprint no. 100 University of Nice. Department of Mathematics.
• 10: M. Cosnard and Y. Robert, "Implementing the Null Space Algorithm over GF(p) on a Ring of Processors", Second international symposium on Computer and Information Sciences, Istanbul (1987).
• 11: M. Cosnard, B. Tourancheau, G. Villard, Présentation de l'hypercube T20 de FPS, Journées Architecture C3, Sophia Antipolis, Revue Bigre + Globule (1987).
• 12: Michel Cosnard , Bernard Tourancheau , G. Villard, Gaussian Elimination on Message Passing Architecture, Proceedings of the 1st International Conference on Supercomputing, p.611-628, June 08-12, 1987
• 13: J. D. Dixon, "Exact solution of Linear Equations using P-adic Expansions", Numer. Math. 40, 137--141 (1982).
• 14: Floating Point Systems, "Programming the FPS T-Series, Release B, Portland Oregon 97223.
• 15: G. A. Geist, "Efficient Parallel LU Factorization with Pivoting on a Hypercube Multiprocessor", ORNL Preprint 6211 (1985).
• 16: G. H. Golub and C. F. Van Loan, "Matrix Computation", The John Hopkins Univ. Press (1983).
• 17: R T. Gregory , E V. Krishnamurthy, Methods and applications of error-free computation, Springer-Verlag New York, Inc., New York, NY, 1984
• 18: K. Hwang and F. Briggs, "Parallel Processing and Computer Architecture", Mc Graw Hill (1984).
• 19: S. L. Johnsson and C. T. Ho, "Spanning Graphs for Optimum Broadcasting and Personalized Communication in Hypercubes", Technical Report 500. Comp. Sc. Dpt., Yale University (1986).
• 20: M. Kaminski, A. Paz, Computing the Hermite normal form on an integral matrix, Technical Report 417, Israel Institute of Technology (june 1987).
• 21: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 22: E. V. Krishnamurthy, T. M. Rao and K. Subramanian, "P-adic Arithmetic Procedures for Exact Matrix Computations", Proc. Indian Acad. Sci. 82A, 165--175 (1975).
• 23: Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
• 24: D. G. Malm, A computer laboratory manual for number theory, student manual, COMPress (1980).
• 25: R. Mœnck "Is a Linked List the Best Storage for an Algebra System" Research Report
• 26: M. Newman, Integral matrices, Pure and applied mathematics, Academic Press (1973).
• 27: Eric Regener, Multiprecision integer division examples using arbitrary radix, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.325-328, Sept. 1984 [doi>10.1145/1271.2738]
• 28: J. L. Roch, P. Sénéchaud, F. Siebert et G. Villard, "Parallel Algebraic Computing", Imag Grenoble, RR--686 I, (december 1987).
• 29: J. L. Roch, P. Senechaud, F. Siebert, G. Villard "Calcul Formel Parallelisme et Occam" OPPT Ed. T. Muntean (1987).
• 30: Y. Saad, Topological properties of hypercubes, Research report YALEU / DCS / RR-389 (1985).
• 31: Y. Saad, Gaussian elimination on hypercubes, Proceedings of the international workshop on Parallel algorithms & architectures, p.5-17, November 1986, Luminy, France
• 32: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 33: Q. F. Stout and B. Wager. "Intensive Hypercube Communication: Prearranged Communication in Link-Bound Machines", CRL-TR-9-87, University of Michigan (1987).
• 34: G. Villard, "Parallel General Solution of Rational Linear Systems using P-adic Expansions", Proceedings of the IFIP WG 10.3 Working Conference on Parallel Processing, Pisa Italy, Elsevier Sc. P. To appear (1988).
• 35: Stephen Michael Watt, Bounded parallelism in computer algebra, University of Waterloo, Waterloo, Ont., Canada, 1986

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Performance, Theory