Large systems of coupled non-linear ordinary differential equations arise naturally in applications areas like design of radio-frequency integrated circuits and vibration analysis of mechanical structures. Of particular interest is the steady-state response of a non-linear system to periodic stimulus -- i.e., the response after any start-up transient has died down. Various classic RF (radio-frequency) measurements -- such as compression point or intermodulation -- only make sense in steady state. The response to quasi-periodic stimulus (two frequencies which are not rationally related) is of special interest in radio work. Exact or even approximate "closed form" solutions of such systems is impossible for realistic examples, due to the size of the problem and the complexity of non-linear models. However, numerical solutions can be highly effective.

The methods of Harmonic Balance or Finite Differencing replace the system of ODEs with a system of non-linear equations using discretization and a suitable numerical approximation to the time derivative. However, the system of equations becomes much larger. If the original system of ODEs had m waveforms (typical m: 100 to 1000) and n discretization points are used (typical n: 32 to 1024) then a solve of m*n non-linear equations in m*n unknowns is required. The dimension of this system can exceed 100,000(!). A numerical method, such as Newton's method, is used to solve the system. Each step of Newton's method (the so-called "outer" iteration) requires the solution to a system of linear equations of the same size as the non-linear system. Conventional Gaussian elimination would flounder on a system of such size. However, the special structure of the linear system allows a very fast matrix-vector product. Therefore, iterative linear solves can be used (the so-called "inner" iteration) to compute the solution to the linear problem needed for each step of Newton's method. The memory and time savings possible with such iterative linear solves is enormous and enables solution of practical problems of a size which was considered unapproachable a few years ago.

I plan to have participants implement a complete steady-state simulation code using iterative linear solves for the inner iteration. I will provide some of the supporting environment for this project and will supply several realistic example problems. Then, various ideas from the theory of structured matrices will be introduced including Toeplitz and circulant matrices, Tensor products, multi-dimensional Fourier transforms and matrices of low displacement rank. Using these concepts, participants will be asked to develop new ideas for improving the performance of the implementation, and try out their ideas on the suite of test problems. No particular knowledge of electrical engineering will be assumed, but participants should be strong programmers comfortable with numerical methods in either C or Fortran. We will begin immediately to look at "industrial strength" examples, large enough so that both asymptotic performance and constant speed improvements are important.

Selected references:

Steady-state Methods for Simulation Analog and Microwave Circuits, K. Kundert, J. White, A. Sangiovanni-Vincentelli, Kluwer Academic Publishers, 1990.
Mathematics of Multi-dimensional Fourier Transforms, R. Tolimieri, M. An, C. Lu, Springer-Verlag, 1993.
IEEE Custom Integrated Circuits Conference (CICC); years 95,96,97; Long,Feldmann,Roychowdhury,Horton,Ashby,Melville.
Iterative Methods for Sparse Linear Systems, Y. Saad, PWS Publishing, 1996.

RF Communication Circuits

Project Team Participants:

Workshop Schedule

Back to Mathematical Modeling in Industry

Back to top of page