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

摘要

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 nxn sparse matrix of dense NxN blocks, such that each block is of size N2. 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 nxn sparse matrix which includes compressed blocks which can be represented by substantially less than N2 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 Nxalpha, where alphaN. 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.