DgParser
DgParser accepts the Single Assignment Programs that are generated by MatParser and converts them into a Polyhedral Reduced Dependence Graph (PRDG). A PRDG representation is much more amenable to mathematical manipulation. For example, on Polyhedral objects, one can operate on them using the following operations: intersections, difference, union, simplify, and image transformations. These polyhedral objects may be parameterized.
An example of a Polyhedra is given in the figure below. It shows a volume, which is defined by for-next statements and If-then-else statements in the QR algorithm for a particular variable (see its
SAC code). Within the volume, there are integral points, given by the black dots. The work of Ehrhart is to get a polynomial expression for the number of integral points in a volume. Loechner et al has extended this work by getting the expression in terms of parameterized polyhedra. (In the example, the parameters are M1 and M2). The Ehrhart polynomial for this volume is equal to ( ( 1/2 * M1 + -1/2 ) * M2^2 + ( -1/2 * M1 + 1/2 ) * M2 + 0 )
This picture is made using the visualization tool
VisuDomain, developed by Vicent Loechner and Stephane Genaund.For the polyhedral representation, we relay on the
Polylib library. For this library, we have created a Java front-end, using JNI (Java Native Interface) to make the Polylib data-structures and operations available within Java. The result of DgParser is given in a XML format. XML is a standard language that is easy to learn and to integrate in tools. Many XML parsers are available.Below are given some examples.