M.Sc Thesis

M.Sc StudentGutterman Zvi
SubjectSymbolic Pre-Computation for Numerical Applications
DepartmentDepartment of Computer Science
Supervisors PROF. Irad Yavneh


In this thesis we study three aspects of symbolic methods for numerical applications. One is the computing of symbolic differentiation. Specifically, we describe SEMT, a software package based on C++ templates, which allows the programmer to create symbolic expressions, substitute variables in them, and compute their derivatives. The unique aspect of SEMT is that these manipulations are all done at compile time. In other words, SEMT effectively coerces the compiler to do symbolic computation as part of the compilation process. Beyond the theoretical interest, SEMT has application in an efficient, generic and easy to use implementation of many numerical algorithms. In the second part of this thesis we show that the problem of compiling C++ programs is Turing complete: for every Turing machine $U$, there exists a C++ program $P$, such that a C++ compiler will halt compiling $P$ if and only if $U$ halts. Therefore, you should not be searching for a different vendor if your C++ compiler gets into an endless loop, or if it sets arbitrary limits on your program. The flaw is with the language. On the positive side, we have that arbitrarily complex computations can be carried out at compile time. The consequence is that a skilled programmer can employ the compiler to do whatever partial evaluation is required for optimizing the runtime. A detailed transition for any Turing Machine into C++ compile time processing using templates is provided. The third aspect is an approach for transforming systems of partial differential equations in order to obtain new formulations which are more accessible to numerical solution. An algorithm is developed for generating such transformations automatically, using symbolic computations employing Gröbner bases. The algorithm is implemented using freely available software.