Low-displacement rank preconditioners for simplified non-linear analysis of circuits and other devices

Abstract

Methods and apparatus for performing non-linear analysis using preconditioners to reduce the computation and storage requirements associated with processing a system of equations. A circuit, system or other device to be analyzed includes n unknown waveforms, each characterized by N coefficients in the system of equations. A Jacobian matrix representative of the system of equations is generated. The Jacobian matrix may be in the form of an n&times;n sparse matrix of dense N&times;N blocks, such that each block is of size N,. In an illustrative embodiment, a low displacement rank preconditioner is applied to the Jacobian matrix in order to provide a preconditioned linear system. The preconditioner may be in the form of an n&times;n sparse matrix which includes compressed blocks which can be represented by substantially less than N,elements. For example, the compressed blocks may each be in the form of a low displacement rank matrix corresponding to a product of two generator matrices having dimension N&times;&agr;, where &agr;<<N. The preconditioned linear system may be solved by factoring the preconditioner using a sparse lower-upper (LU) factorization or other similar sparse factorization method applied to the compressed blocks.