An Implementation of MacMahon's Partition Analysis in Ordering the Lower Bound of Processing Elements for the Algorithm of LU Decomposition

Authors: Halil Snopce, Ilir Spahiu, Lavdrim Elmazi

Abstract:

A lot of Scientific and Engineering problems require the solution of large systems of linear equations of the form bAx in an effective manner. LU-Decomposition offers good choices for solving this problem. Our approach is to find the lower bound of processing elements needed for this purpose. Here is used the so called Omega calculus, as a computational method for solving problems via their corresponding Diophantine relation. From the corresponding algorithm is formed a system of linear diophantine equalities using the domain of computation which is given by the set of lattice points inside the polyhedron. Then is run the Mathematica program DiophantineGF.m. This program calculates the generating function from which is possible to find the number of solutions to the system of Diophantine equalities, which in fact gives the lower bound for the number of processors needed for the corresponding algorithm. There is given a mathematical explanation of the problem as well. Keywordsgenerating function, lattice points in polyhedron, lower bound of processor elements, system of Diophantine equationsand : calculus.

Keywords: generating function, lattice points in polyhedron, lower bound of processor elements, system of Diophantine equations and calculus.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060822

References:

1] M.P. Bekakos, Highly Parallel Computations-Algorithms and Applications, Democritus University of Thrace, Greece, pp. 139-209, 2001.
[2] N. Petkov, Systolic Parallel Processing, North-Holland, 1993
[3] Special issue on: The Future of Micro-Processors, Computer, vol. 30, no.9, September 1997
[4] S.Y.Kung, VLSI Array Processors, Prentice-Hall, Englewood Cliffs, New Jersey, 1988.
[5] Kung, H.T. and Leiserson, C.E., Systolic arrays for (VLSI), Introduction to VLSI Systems, Addison-Wesley Ltd., Reading, MA, 1980.
[6] W. Shang, J.A.B. Fortes, Time optimal linear schedule for algorithms with uniform dependencies, IEEE Trans. Comput. 40 (6) (1991) 723-742.
[7] C. Scheiman, P. Cappello, A processor-time minimal systolic array for the 3D rectilinear mesh, in: Proc. Int. Conf. On Application Specific Array Processors, Strasbourg, France, July, 1995, pp.26-33
[8] C. Scheiman, P. Cappello, A period processor-time minimal schedule for cubical mesh algorithms, IEEE Trans. Comput. 40 (6) (1991) 723-742.
[9] C. Scheiman, P. Cappello, A processor-time minimal systolic array for transitive closure, IEEE Trans. Parallel Distributed Syst. 3 (3) (1992) 257-269.
[10] A. Benaini, Y. Robert, Spacetime-minimal systolic arrays for Gaussian elimination and the algebric path problem, in: Proc. Int. conf. On Application Specific Array Processors, IEEE Computer Society, Princeton, 1990, pp. 746-757.
[11] P. Cappello, Omer Egecioglu, Processor lower bound formulas for array computations and parametric Diophantine systems, Int. J. Found. Comput. Sci. 9 (4) (1998) 351-378
[12] Ph. Clauss, C. Mongenet, G.R. Perrin, Calculus of space-optimal mappings of systolic algorithms on processor arrays, in: Proc. Int. Conf. on Application Specific Array Processors, IEEE Computer Society, Princeton, 1990, pp. 4-18
[13] K. Down, High Performance Computing, O Reilly & Associates, Inc., California, 1993
[14] P. Clauss, V. Loechner, Parametric analysis of polyhedral iteration spaces, J. VLSI Signal Process. 19 (1998) 179-194
[15] D.K. Wilde, A library for doing polyhedral operations, Masters thesis, Corvallis, Oregon, December 1993, Also published as IRISA technical report PI 785, Rennes, France, December 1993
[16] R.P. Stanley, Linear Homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973) 607-632
[17] Major Percy A. Macmahon, F.R.S., D.Sc., LL.D., Combinatory Analysis, volume II, Cambridge University Press, 1916 (Reprinted: Chelsea, New York, 1960)
[18] George E. Andrews, Peter Paule, A. Riese, MacMahons Partition Analysis: The Omega Package, European Journal of Combinatorics, October 2001, vol. 22, iss. 7, pp. 887-904 (18) Academic press., London
[19] G.E, Andrews, MacMahons Partition Analysis II: Fundamental Theorems, Ann. Comb. 4 (2000), 327-338.
[20] Guouce Xin, A Fast Algorithm for MacMahons Partition Analysis. Elect. Journal of Comb. (11), 2004, R58, 20 pp.
[21] Richard L. Burden, J. Douglas Faires, Numerical Analysis, 6th edition, 1997.
[22] Philippe Clauss and Vincent Loechner. Parametric analysis of polyhedral iteration spaces. Journal of VLSI Signal Processing, 19:179-194, 1998.