The importance of using the “omega calculus” in computer algebra
Küçük Resim Yok
Tarih
2009
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Maltepe Üniversitesi
Erişim Hakkı
CC0 1.0 Universal
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Özet
In his book ”Combinatory Analysis”, Percy A. MacMahon developed the so called ”Omega calculus”. In this contribution we emphasize the importance of the ”Omega Calculus”. Using the properties of this tool, we investigate the possible aplication in computer algebra.We investigate how the methods presented by Macmahon’s can be applied to the problem of enumerating lattice points in convex polyhedron. A lot of Scientific and Engineering problems require the solution of large systems of linear equations of the form Ax=b in an effective manner. LU-Decomposition offers good choices for solving this problem. QR Factorization has implementation in various problems of linear algebra. Discrete Fourier transformation can be implemented in different problems regarding the signal and image processing, pattern recognition etc. We investigate a possible optimization of these problems finding the lower bound of processing elements (PEs) required by a schedule as a function of n. From a given algorithm, defining a corresponding index space, we consider that the elements of that index space are lattice points inside 3-dimensional convex polyhedron. The faces of the polyhedron are defined by the inequalities which are the consequence of the given algorithm. From these inequalities augmenting by the condition of linear schedule for the corresponding dag, we convert the geometrical interpretation of the problem, into a combinatorial interpretation, exactly into finding of solutions to the system of Diophantine equations. Then we 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 achieving a given schedule. We give a mathematical explanation and then we confirm the conclusion taking a random example.
Açıklama
Anahtar Kelimeler
Kaynak
International Conference of Mathematical Sciences
WoS Q Değeri
Scopus Q Değeri
Cilt
Sayı
Künye
Snopce, H., Spahiu, I. ve Aliu, A. (2009). The importance of using the “omega calculus” in computer algebra. Maltepe Üniversitesi. s. 187.
