Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1997-11-20
2001-01-30
Lintz, Paul R. (Department: 2768)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S002000, C703S014000, C708S802000
Reexamination Certificate
active
06182270
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to analysis techniques for determining the steady-state response of non-linear electronic circuits, networks, systems or other devices, and more particularly to steady-state analysis techniques based on iterative linear solvers which utilize preconditioners to simplify the analysis process.
BACKGROUND OF THE INVENTION
A variety of numerical analysis methods have been developed for determining the steady-state response of non-linear electronic circuits, networks and other devices. These methods include, for example, finite differencing and harmonic balance techniques. These and other steady-state analysis methods generally involve solving a boundary-value problem on a system of non-linear ordinary differential equations or differential algebraic equations. Each of the methods typically generates a large linear system of equations which needs to be solved many times during a so-called “outer” iteration of the method as it finds the solution to the system of non-linear equations. The large linear system of equations can usually be characterized as a Jacobian matrix of partial derivatives of the non-linear system, and the solution of the Jacobian matrix is a major computational bottleneck in the steady-state analysis process. For steady-state simulation of an electrical network or integrated circuit of even moderate complexity, the Jacobian matrices can be extremely difficult to solve using direct factorization.
An alternative approach to direct factorization of the Jacobian matrix involves the use of iterative linear solution methods, also referred to as iterative linear “solvers.” Although Jacobian matrices are often very large, these matrices are typically structured in a manner which facilitates fast matrix-vector multiplication, and can therefore be solved using well-known iterative linear solution methods such as the QMR or GMRES algorithms. The speed and robustness of these and other iterative linear methods can depend critically on the choice of a preconditioner, which is used to generate a relatively easy-to-invert approximation to a given Jacobian matrix. Unfortunately, conventional preconditioning techniques provide insufficient reductions in computational complexity. As a result, steady-state analysis using iterative linear solution methods remains unduly computationally intensive and therefore impractical in a wide variety of important applications.
SUMMARY OF THE INVENTION
The invention utilizes appropriately-selected preconditioners to reduce the storage and computation requirements associated with non-linear analysis techniques such as finite differencing and harmonic balance. In accordance with the invention, a low displacement rank or other suitable preconditioner is in the form of a matrix of compressed blocks. The preconditioner is applied to a Jacobian matrix representation of a circuit, system or other device to be analyzed, in order to generate a preconditioned linear system which can be solved efficiently using an iterative linear solution method employing the compressed blocks of the preconditioner matrix. This substantially reduces the storage and computation requirements which would otherwise be associated with processing the Jacobian matrix.
In an illustrative embodiment of the invention, the device being analyzed may be characterized by n unknowns with N coefficients used to represent each of the unknowns, and the Jacobian matrix may be in the form of a sparse n×n matrix of dense N×N blocks. A low displacement rank preconditioner is used to generate the preconditioned system based on the Jacobian matrix. The low displacement rank preconditioner has a matrix structure which approximates that of a circulant matrix, but can capture more information from the Jacobian matrix than a conventional preconditioner. For example, the preconditioner may be in the form of a sparse n×n matrix of compressed low displacement rank blocks. Each of the compressed blocks may have a structure corresponding to the product of two generator matrices of dimension &agr;×N, where &agr;<<N, such that each of the blocks in the preconditioner can be represented by substantially less than N
2
elements. The preconditioned system can then be solved by factoring the preconditioner matrix using a conventional sparse lower-upper (LU) factorization or other similar technique operating on the compressed blocks. In accordance with the invention, processing operations can thus be performed on compressed blocks which are effectively of a size <<N
2
, rather than the size N
2
blocks of the original Jacobian matrix, and therefore with substantially reduced storage and computation requirements. The invention may also utilize other types of preconditioners to generate a preconditioned linear system which can be solved using operations on compressed blocks.
REFERENCES:
patent: 5136538 (1992-08-01), Karmarkar et al.
patent: 5604911 (1997-02-01), Ushiro
patent: 5867416 (1999-02-01), Feldmann et al.
M. Rosch, “Schnelle des Stationare Simulation Nichtlinearer Schaltungen,” Dissertation, Technical University of Munich, 1992, vol. 46, No. 3, May 1992, pp. 168-176.
PTO 99-5358 (English translation of the article by M. Rosch and K. Antreich, “Schnelle Stationare Simulation Nichtlinearer Schaltungen im Freuenzebereich,” AEU, vol. 46, No. 3, pp. 1680176, 1992, translated by The Ralph McElroy Translation Company, Sep. 1999.
PTO 99-5369 (English translation of the German article by M. Rosch, “Schnelle Simulation des Stationaren Verhaltens Nichtlinearer Schaltungen,” Dissertation, Technical University of Munich, 1992, translated by Schreiber Translations, Inc., Translated Nov. 1999.
Feldmann et al. (“Efficient Frequency Domain Analysis of Large Nonlinear Analog Circuits”, Proceedings of the IEEE Custom Integrated Circuits Conference, May 1996, pp. 1-4).
Brachtendorf et al. (“A simulation tool for the analysis and verification of the steady state of circuit designs”, International Journal of Circuit Theory and Applications, vol. 23, pp. 311-323, Jan. 1995).
Gremban et al. (“Performance Evaluation of a New Parallel Preconditioner”, NTIS, 34 pages, Oct. 1, 1994).
Gover et al. (“Displacement rank and quasitriangular decomposition for r-Toeplitz matrices”, Linear Algebra Applic., vol. 88-89, pp. 329-348, Jan. 1, 1987.
K.S. Kundert, J.K. White and A. Sangiovanni-Vincentelli, “Steady-State Methods for Simulating Analog and Microwave Circuits,” Kluwer, Boston, MA, pp. 91-93, 124-132, 1990.
V. Rizzoli, C. Cecchetti, A. Lipparini and F. Mastri, “General-Purpose Harmonic Balance Analysis of Nonlinear Microwave Circuits Under Multitone Excitation,” IEEE Trans. Microwave Theory and Tech., vol. MTT-36, No. 12, pp. 1650-1660, Dec. 1988.
V. Rizzoli, F. Mastri, F. Sgallari and V. Frontini, “The Exploitation of Sparse Matrix Techniques in Conjunction with the Piece- Wise Harmonic Balance Method for Nonlinear Microwave Circuit Analysis,” IEEE MTT-S Int. Microwave Symp. Digest, Dallas, TX, pp. 1295-1298, May 1990.
D. Long, R. Melville, K. Ashby and B. Horton, “Full-chip Harmonic Balance,” Proceedings of the IEEE Custom Integrated Circuits Conference, May 1997.
P. Feldmann, R. Melville and D. Long, “Efficient Frequency Domain Analysis of Large Non-Linear Analog Circuits,” Proceedings of the IEEE Custom Integrated Circuits Conference, May 1996.
R. Melville, P. Feldmann and J. Roychowdhury, “Efficient Multi-Tone Distortion Analysis of Analog Integrated Circuits,”Proceedings of the IEEE Custom Integrated Circuit Conference, May 1995, pp. 1-4.
M. Rösch and K. Antreich, “Schnelle Stationare Simulation Nichtlinearer Schaltungen im Freuenzebereich,” AEU, vol. 46, No. 3, pp. 168-176, 1992.
T. Kailath and A. Sayed, “Displacement Structure: Theory and Applications,” SIAM Review, vol. 37, No. 3, pp. 297-386, Sep. 1995.
I. Gohberg and V. Olshevsky, “Circulants, Displacements and Decompositions of Matrices,” Integr. Equat. Oper. Th, vol. 15, pp. 730-743, Birkhauser Verlag, Basel, 1992.
I. Gohberg and V. Olshevsky, “Complexity of Multiplicatio
Feldmann Peter
Long David Esley
Melville Robert C.
Kik Phallaka
Lintz Paul R.
Lucent Technologies - Inc.
Ryan & Mason & Lewis, LLP
LandOfFree
Low-displacement rank preconditioners for simplified... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Low-displacement rank preconditioners for simplified..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-displacement rank preconditioners for simplified... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555861