Introduction to Model Order Reduction

Instructor: Prof. Luca Daniel

Affiliation: Electrical Engineering and Computer Science Department of the Massachusetts Institute of Technology

Duration: 15 hours

Period: June 19 - June 23, 2006

Place: Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via G. Caruso, meeting room, ground floor

Time: 14:00 – 17:00

Credits: 4

Contacts: Ing. F. De Bernardinis, Ing. P. Nuzzo

 

Description

The performance of many large engineering systems and complex components often critically depends on what the designers like to address as “second order effects”. These are typically phenomena that can be captured accurately only by computationally demanding partial differential equation solvers (e.g. Maxwell, Nevier-Stokes, or heat diffusion field solvers). Designers, however, would greatly benefit from the availability of very small models that capture the input-output behavior of complex systems with the same accuracy as field solvers. In this series of lectures we will survey several techniques to generate automatically such reduced order models preserving field solver accuracy. We will further describe techniques to generate field solver accurate parameterized reduced order models that can be instantiated for a range of values of specified design parameters, hence enabling fast design exploration and optimization. Detailed examples will be presented, drawn from a variety of engineering disciplines e.g. Electrical Engineering (interconnect networks including parasitics; fullwave electromagnetic structures; analog and digital circuits including nonlinear semiconductor devices and Micro-Electro-Mechanical Devices), Mechanical Engineering (frame modeling, heat diffusion), and Civil Engineering (structural problems).

 

Outline

PART I: Assembling Dynamical State Space Systems from Engineering problems

1.      Motivations and sample problems from Electrical, Mechanical and Civil Engineering.

2.      Assembling automatically System Models:

    1. from modified nodal analysis MNA
    2. from Partial Differential Equation (PDE) solvers (e.g. Finite Difference, Finite Element). 

3.      Basic techniques for numerical analysis for systems models:

    1. Steady State Analysis of Linear System Models (LU decomposition, Krylov iterative methods);
    2. Steady State Analysis of Non-Linear System Models (Newton method);
    3. Time domain simulation of Dynamical Systems Models.

4.      Important properties of some physical Dynamical Systems (e.g. stability, passivity).

PART II: Model Order Reduction of Linear Dynamical Systems

1.      Reducing Linear Time Invariant (LTI) Systems

    1. Modal analysis (the eigenvalue method).
    2. Rational function fitting (Point Matching).
    3. Quasi-convex optimization methods.
    4. Pade’ approximation and Asymptotic Waveform Evaluation (AWE).

2.      Reducing LTI Systems with the Projection Framework.

    1. The Projection Framework.
    2. Proper Orthogonal Decomposition (POD), or Karhunen-Lo`eve decomposition (KLD), or principal component analysis (PCA), or singular value decomposition (SVD).
    3. Transfer Function Moment Matching (PVL).
    4. Passivity and stability preserving Moment Matching (PRIMA)
    5. Truncated Balance Realizations (TBR).
    6. Positive Real and Bounded Real TBR to preserve passivity.  

3.      Reducing LTI Distributed Systems (with frequency dependent matrices)

PART III: Model Order Reduction of Non-Linear Dynamical Systems.

1.      Introduction, Examples, and Definitions

2.      Reduction of Weakly Non-Linear Dynamical Systems (Volterra Series).

3.      Trajectory Piece-Wise Linear (TPWL) + moment matching reduction.

4.      Trajectory Piece-Wise Linear (TPWL) + balance realizations (TBR) reduction.

PART IV: Model Order Reduction of Parameterized Dynamical Systems.

1.      Motivations, applications and problem classification.

2.      Reducing Linear Systems

    1. Reducing linear models with linear dependency on parameters.
    2. Reducing linear models with non-linear dependency on parameters.
    3. Parameterized Quasi-convex optimization based approach. 

3.      Reducing non-linear models with non-linear dependency on parameters.

 

 

References:

 

ASSEMBLING AND WORKING WITH DYNAMICAL STATE SPACE SYSTEMS

  1. L. N. Trefethen, D. Bau, Numerical Linear Algebra, SIAM, 1997.
  2. Luca Daniel, "Simulation and Modeling Techniques for Signal Integrity and Electromagnetic Interference on High Frequency Electronic Systems," Ph.D. Thesis, University of California at Berkeley, May 2003. [Chapters 2, 3, 7, 8, 9, 10.]
  3. J. C. Willems, “Dissipative dynamical systems,” Arch. Rational Mechanics Anal., vol. 45, pp. 321–393, 1972.

 

MODEL ORDER REDUCTION OF LINEAR DYNAMICAL SYSTEMS

  1. C. P. Coelho, J. R. Phillips, and L. M. Silveira, “A convex programming approach to positive real rational approximation,” in Int. Conf. on Computer Aided-Design, San Jose, CA, Nov. 2001, pp. 245–251.
  2. Liang,Y.C.,Lee,H.P.,Lim,S.P.,Lin,W.Z.,Lee,K.H.and Wu, C.G.,“Proper Orthogonal Decomposition and its Applications-Part I:Theory ”,Journal of Sound and Vibration (2002)252(3),page 527-544.
  3. E. Grimme, “Krylov projection methods for model reduction,” Ph.D. dissertation, Coordinated-Science Laboratory, Univ. of Illinois at Urbana-Champaign, IL, 1997.
  4. P. Feldmann, R. W. Freund, “Efficient linear circuit analysis by Padé approximation via the Lanczos process,” IEEE Trans. Computer-Aided Design, vol. 14, pp. 639–649, May 1995.
  5. A. Odabasioglu, M. Celik, and L. T. Pileggi, “PRIMA: Passive reduced-order interconnect macromodeling algorithm,” IEEE Trans. Computer-Aided Design, vol. 17, pp. 645–654, Aug. 1998.
  6. L. Daniel, J. Phillips, "Model Order Reduction for Strictly Passive and Causal Distributed Systems", IEEE/ACM 39th Design Automation Conference, New Orleans, Jun 2002.
  7. J. M. Wang, C..C. Chu, Q. Yu, E. S. Kuh, “On Projection-Based Algorithms for Model-Order Reduction of Interconnects”, IEEE Trans. on Circuit and Systems-I, Vol 49, no 11, Nov 2002.
  8. B. Moore, “Principal component analysis in linear systems: Controllability, observability, and model reduction,” IEEE Trans. Automat. Contr., vol. AC-26, pp. 17–32, Feb. 1981.
  9. J. Phillips, L. Daniel, L. M. Silveira, "Guaranteed Passive Balancing Transformations for Model Order Reduction", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 22, No. 8, Aug 2003.
  10. K. Glover, “All optimal Hankel-norm approximations of linear multi-variable systems and their L -error bounds,” Int. J. Control, vol. 39, no. 6, pp. 1115–1193, June 1984.
  11. J.-R Li, F. Wang, J. White, “Efficient model reduction of interconnect via approximate system Grammians,” in Int. Conf. Computer Aided-Design, San Jose, CA, November 1999, pp. 380–383.
  12. J. R. Phillips, “Model reduction of time-varying linear systems using approximate multipoint Krylov-subspace projectors,” in Int. Conf. on Computer Aided-Design, Santa Clara, CA, Nov. 1998, pp. 96–102.

 

MODEL ORDER REDUCTION OF NON-LINEAR DYNAMICAL SYSTEMS

  1. J. R. Phillips, “Projection frameworks for model reduction of weakly nonlinear systems,” in 37th ACM/IEEE Design Automation Conf., 2000, pp. 184–189.
  2. M. Rewienski and J. White, "A Trajectory Piecewise-linear Approach to Model Order Reduction and Fast Simulation of Nonlinear Circuits and Micromachined devices," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 22, No. 2, pp. 155--170, Feb. 2003.
  3. N. Dong and J. Roychowdhury, “Piecewise polynomial nonlinear model reduction.” ACM/IEEE Design Automation Conference, June 2003.

 

MODEL ORDER REDUCTION OF PARAMETERIZED SYSTEMS

  1. L. Daniel, C. S. Ong, S. C. Low, K. H. Lee, J. White, “A Multiparameter Moment Matching Model Reduction Approach for Generating Geometrically Parameterized Interconnect Performance Models", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, v 23, n 5, p 678-93, May 2004.
  2. L. Daniel, J. White, "Automatic generation of geometrically parameterized reduced order models for integrated spiral RF-inductors", Proceedings of the 2003 IEEE International Workshop on Behavioral Modeling and Simulation, p 18-23, San Jose, CA, 2003.
  3. P. Li, F. Liu, S. Nassif, and L. Pileggi. “Modeling interconnect variability using efficient parametric model order reduction”. In Design, Automation and Test Conference in Europe, March 2005.
  4. P. Rabiei and M. Pedram, “Model reduction of variable-geometry interconnects using variational spectrally-weighted balanced truncation,” in Int. Conf. Computer Aided-Design, San Jose, CA, Nov. 2001, pp. 586–591.
  5. Sou, K, Megretski, A, Daniel, L, "A Quasi-Convex Optimization Approach to Parameterized Model Order Reduction", IEEE/ACM Design Automation Conference, Anaheim, CA, (2005).
  6. B. Bond and L. Daniel, "Parameterized Model Order Reduction of Nonlinear Dynamical Systems", Proceedings of the IEEE Conference on Computer-Aided Design, San Jose, (2005)