For a wide variety of micromachined devices, designers need accurate analysis of fluid drag forces for complicated three-dimensional (3-D) problems. This paper describes FastStokes, a recently developed 3-D fluid analysis program. FastStokes rapidly computes drag forces on complicated structures by solving an integral formulation of the Stokes equation using a precorrected fast Fourier transform (PFFT)-accelerated boundary element method (BEM). The specializations of the PFFT algorithm to the Stokes flow problem are described, and computational results are presented. Timing results are used to demonstrate that FastStokes scales almost linearly with problem complexity, can easily analyze structures as complicated as an entire comb drive in under an hour, and can produce results that accurately match measured data.

More aggressive design practices have created renewed interest in techniques for analyzing substrate coupling problems. Most previous work has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting resistance matrix, whose number of nonzero entries grows quadratically with the number of contacts. Wavelet-like methods have been applied to sparsifying the resistance matrix representing the substrate coupling, but the accuracy of the method is very sensitive to the particulars of the contact layout. In this paper we show that for the substrate problem it is possible to improve considerably on the wavelet-like methods by making use of the algorithmic structure common to the fast multipole and wavelet-like algorithms, but making judicious use of low-rank approximations. The approach, motivated by the hierarchical SVD algorithm, can achieve more than an order of magnitude better accuracy for commensurate sparsity, or can achieve much better sparsity at commensurate accuracy, when compared to the wavelet-like algorithm.

The sudden increase in systems-on-a-chip designs has renewed interest in techniques for analyzing and eliminating substrate coupling problems. Previous work on the substrate coupling analysis has focused primarily on faster techniques for extracting coupling resistances, but has offered little help for reducing the resulting network whose number of resistors grows quadratically with the number of contacts. In this paper we show that an approach inspired by wavelets can be used in two ways. First, the wavelet method can be used to accurately sparsify the dense contact conductance matrix. In addition, we show that the method can be used to compute the sparse representation directly. Computational results are presented that show that for a problems with a few thousand contacts, the method can be almost ten times faster at constructing the matrix.