Global node reduction of linear systems using ratio analysis

Linear systems are widely used in mathematics and engineering. Constructing a minimal directed acyclic graph (DAG) that corresponds to a given linear system is important in high-level synthesis. It is shown to be NP-complete. Ratio analysis, a novel multi-step algorithm for constructing a small sized DAG is presented. Ratio analysis attempts to minimize the total number of nodes in a DAG by maximizing the sharing of nodes between equations. The first part of the algorithm considers the ratio of terms in different equations. The second part looks at the difference between these ratios and the final equations. The third part generates the final DAG. Results are shown that illustrate the efficiency of the algorithm as well as the savings which are possible from the algorithm´s application