I. Introduction
Process variations have become a major concern in submicronmeter and nano-scale chip design [2]–[6]. In order to improve chip performances, it is highly desirable to develop efficient stochastic simulators to quantify the uncertainties of integrated circuits and microelectromechanical systems (MEMS). Recently, stochastic spectral methods [7]–[12] have emerged as a promising alternative to Monte Carlo techniques [13]. The key idea is to represent the stochastic solution as a linear combination of some basis functions e.g., generalized polynomial chaos (gPC) [8], and then compute the solution by stochastic Galerkin [7], stochastic collocation [9]–[12], or stochastic testing [14]–[16] methods. Due to the fast convergence rate, such techniques have been successfully applied in the stochastic analysis of integrated circuits [14]–[20], very large scale integration interconnects [21]–[25], electromagnetic [26], and MEMS devices [1], [27], achieving significant speedup over Monte Carlo when the parameter dimensionality is small or medium.