We propose two efficient automatic differentiation (AD) schemes to compute incrementally Taylor series and System Jacobian for solving differential-algebraic equations (DAEs) by Taylor series. Our schemes are based on topological ordering of a DAE's computational graph and then partitioning the topologically sorted nodes using structural information obtained from the DAE. Solving a DAE by Taylor series is carried out in stages. From one stage to another, partitions of the computational graph are incrementally activated so that we can reuse Taylor coefficients and gradients computed in previous stages. As a result, the computational complexity of evaluating a System Jacobian is independent of the number of stages. We also develop a common subexpression elimination (CSE) method to build a compact computational graph through operator overloading. The CSE method is of linear time complexity, which makes it suitable as a preprocessing step for general operator overloaded computing. By applying CSE, all successive overloaded computation can save time and memory. Furthermore, the computational graph of a DAE reveals its internal sparsity structure. Based on it, we devise an algorithm to propagate gradients in the forward mode of AD using compressed vectors. This algorithm can save both time and memory when computing the System Jacobian for sparse DAEs. We have integrated our approaches into the \daets solver. Computational results show multiple-fold speedups against two popular AD tools, \FAD~and ADOL-C, when solving various sparse and dense DAEs. / Thesis / Master of Science (MSc)

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.