A Semidirect Biharmonic Solver for VLSI

Wednesday, June 11, 1997 - 2:20pm - 2:40pm
Keller 3-180
Marian Vajtersic (Slovak Academy of Sciences (SAV))
An efficient VLSI algorithm for solving the model biharmonic problem will be presented. The complexity of this VLSI solver will be characterized in terms of the area $times$ time measure $A{T^2}$, where $A$ and $T$ stand respectively for the {it time} and the {it area} required for the parallel algorithm.

The first boundary value problem for the biharmonic equation will be considered for a rectangular domain with $ntimes n$ interior grid points. The VLSI algorithm is based on the semidirect approach which treats the biharmonic operator as a coupled pair of Laplace operators.

The design is of a compact form where one VLSI block performs all operations of the semidirect cycle. Its length and height are proportional to $O(n{ log n}) $. The total parallel computational time is $O(sqrt{n}{ log}^2n)$. Hence, the global estimation in $A{T^2}$ complexity measure is $O({n^3}{{ log}^6n})$ for this algorithm. This represents the best $A{T^2}$ upper bound for the biharmonic problem until now.