Efficiency estimate for distributed computation of Gröbner bases and involutive bases
Tóm tắt
Several years ago, we presented a program complex for parallel computation of Gröbner bases that works on computers with shared-memory architecture. Unfortunately, the number of the processors that we can use is small (from 2 to 16) because of hardware constraints. This paper presents a program for distributed computation of bases that relies on the same principles but works in a network consisting of heterogeneous machines. The effectiveness of such an approach is estimated from the standpoint of the processor capacity usage and the required network bandwidth, and methods optimizing usage of these resources are specified.
Tài liệu tham khảo
Attardi, G. and Traverso, C., A Strategy-Accurate Parallel Buchberger Algorithm, Lecture Notes Series in Computing (PASCO’94), vol. 5, Singapore: World Sci., 1994, pp. 49–54.
Faugère, J.C., Parallelization of Gröbner Basis, Lecture Notes Series in Computing (PASCO’94), vol. 5, Singapore: World Sci., 1994, pp. 124–132.
Amrheim, B., Gloor O., and Küchlin, W., A Case Study of Multi-Threaded Gröbner Basis Completion, Proc. of ISSAC’96, ACM, 1996, pp. 95–102.
Leykin, A., Algorithms in Computational Algebraic Analysis, Ph.D. Gissertation, University of Minnesota, 2003.
Buchberger, B., Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, Recent Trends in Multidimensional System Theory, Bose, N.K., Ed., Dordrecht: Reidel, 1985, pp. 184–232.
Gerdt, V.P. and Blinkov, Yu.A., Involutive Bases of Polynomial Ideals, Math. Comput. Simulation, 1998, vol. 45, pp. 519–542.
Gerdt, V.P., Involutive Algorithms for Computing Gröbner Bases, Computational Commutative and Non-Commutative Algebraic Geometry, Cojocaru, S., Pfister, G., and Ufnarovski, V., Eds., Amsterdam: IOS, 2005, pp. 199–225.
Gerdt, V.P. and Yanovich, D.A., Parallelism in Computing Janet Bases, Proc. of CAAP’01, 2001, Dubna, Russia.
Yanovich, D.A., Parallelization of an Algorithm for Computation of Involutive Janet Bases, Programmirovanie, 2002, no. 2, pp. 16–20. [Programming Comput. Software (Engl. Transl.), 2002, vol. 28, no. 2, pp. 66–69].
Gerdt, V.P. and Yanovich, D.A., Parallel Computation of Involutive and Gröbner Bases, Computer Algebra in Scientific Computing (CASC 2004), Ganzha, V.G., Mayr, E.W., and Vorozhtsov, E.V., Eds., Institute of Informatics, Technical University of Munich, Garching, 2004, pp. 185–194.
http://en.wikipedia.org/wiki/Symmetric_multiprocessing.
List of Distributed Computing Projects, http://en.wikipedia.org/wiki/List_of_distributed_computing_projects.
Janet, M., Leçons sur les Systèmes d’Equations aux Dérivées Partielles, Cahiers Scientifiques, IV, Paris: Gauthier-Villars, 1929.
Gerdt, V.P. and Blinkov, Yu.A., Involutive Divisions of Monomials, Programmirovanie, 1998, no. 6, pp. 22–24.
Gerdt, V.P. and Blinkov, Yu.A., Minimal Involutive Bases, Math. Comput. Simulation, 1998, vol. 45, pp. 543–560.
Bini, D. and Mourrain, B., Polynomial Test Suite, 1996, http://www-sop.inria.fr/saga/POL.
Verschelde, J., The Database with Test Examples, http://www.math.uic.edu/:_jan/demo.html.