UNIFIED ARCHITECTURE FOR DIVIDE-AND-CONQUER BASED TRIDIAGONAL SYSTEM SOLVERS

The solution of tridiagonal systems is a topic of great interest in ma ny areas of numerical analysis. Several algorithms have recently been proposed for solving triadiagonal systems based on the Divide and Conq uer (DC) strategy, In this work we propose an unified parallel archite cture for DC algorithms which present the data flows of the Successive Doubling, Recursive Doubling and Parallel Cyclic Reduction methods, T he architecture is based in the perfect unshuffle permutation, which t ransforms these data flows into a constant geometry one, The partition of the data arises in a natural manner, giving way to a systolic data how with a wired control section, We conclude that the constant geome try Cyclic Reduction architecture is the most appropriate one for solv ing tridiagonal systems and, from the point of view of integration in VLSI technology, is the one which uses the least amount of area and th e smallest number of pins.