Nonlinear Methods

From Model order reduction site at MIT

Jump to: navigation, search

Contents

Introduction

The nonlinear MOR problem is the problem concerning more general description of dynamical systems:

\begin{cases} \frac{dx(t)}{dt} = f(x(t),u(t)), & x(t) \in \mathbb R^n, \; u(t) \in \mathbb R^m \\ y(t) = g(x(t),u(t)), & y(t) \in \mathbb R^l \end{cases} \qquad (1)

Sometimes (for example, when simulating circuit with nonlinear capacitors) the original equation has even more complex form:

\begin{cases} h(\dot x(t), x(t)) = f(x(t),u(t)), & x(t) \in \mathbb R^n, \; u(t) \in \mathbb R^m \\ y(t) = g(x(t),u(t)), & y(t) \in \mathbb R^l \end{cases} \qquad (2)

The desired goal, in general, is to accelerate the simulation of the system (1) or (2). Though we will call this model order reduction, there are really two different aspects to this problem, in general. First is the cost associated with the high dimensionality of x, as we had with the linear dynamical systems. Lower order would generally lead to lower computational costs. Another cost is associated with the speed of calculating functions f(\cdot,\cdot) and (if applicable) h(\cdot, \cdot) along with their derivatives (which are usually needed for popular ODE solvers based on Backward Euler or trapezoid rule time integration schemes). We neglect the costs associated with the function g(\cdot, \cdot), since usually it is a straightforward computation.

In the linear model reduction we neglected the costs associated with computing f(\cdot,\cdot), because by using an eigenvalue decomposition we can always make matrix A in f(x,u) \equiv Ax + Bu tri-diagonal, therefore evaluating right-hand side is fast, and solvng the system is fast, too when sparse solver is employed.

Unfortunately, for nonlinear problems we do care how fast the function f(\cdot,\cdot) can be computed. Moreover, when solving ODE (1) or (2), we usually need to be able to compute Jacobians (derivatives with respect to x) of f(\cdot,\cdot) and h(\cdot,\cdot) if backward-Euler or trapezoid rule time integration is used. These rules are most widely used in practice, due to their numerical stability properties.

Projection

The only known practical approach of doing nonlinear model reduction is based on projections. In the linear reduction domain, there exist other alternatives, though they are much rarely used, due to ill-conditioned operations involved, for example computing matrix inverse.

Let's assume that we would like to perform a projection of the system (1) using some projection matrices W \in \mathbb R^{n \times q} and V such that WTV = I. As we did for the linear systems, we assume that x evolves approximately in the range (column span) of matrix V and therefore we approximate the state as

x \approx Vz.

Again, similarly to the linear MOR, we project the residual using WT, and get the following reduced dynamical system:

\begin{cases} \frac{dz(t)}{dt} = \underbrace{W^Tf(Vz(t),u(t))}_{f^r(z(t), u(t))}, & z(t) \in \mathbb R^q, \\ y^r(t) = g(Vz(t),u(t)) \end{cases} \qquad (3)

We have reduced the dimensionality of the state: instead of x, which was of dimension n, we now have an ODE with the state z having only q components(q \ll n).

For general nonlinear systems, if one would implement MOR in the form (3) in the simulator, the actual increase in speed would not be nearly as dramatic as the speed-up for linear systems for similar reduction in the state dimensionality. The problem is the complexity of evaluating fr(z(t),u(t)). In order to evaluate it for a given point z(t), we need to evaluate the original f(x(t),u(t)), then project back the long (order n) vector of derivatives of x. The same concerns the system's Jacobian. Despite the reduced dimensionality of the state, the issue of efficiency of evaluation of the right-hand side (mentioned in the introduction) becomes a bottleneck. We need to find a more efficient representation of the function fr(z(t),u(t)), which is fast to compute, without reference to the original high-dimensional state-space.

There are two major approaches to this problem:

  • Use of the Taylor expansion of f(x,u)
  • Use of the trajectory piecewise-linear method(or, more generally, kernel-based approximation) of function fr.

Taylor expansion-based methods

TPWL methods

Choice of projection matrices

Conclusions

Nonlinear model order reduction is the most challenging topic. Very good review of nonlinear MOR methods is presented in the thesis of Michal Rewienski . The major trade-off is that the techniques are either applicable to only weakly-nonlinear systems (such as Volterra-series based or polynomial expansion-based methods), or they work only for some input signals close to some special training input, which was used during model extraction (as with Trajectory Piecewise model order reduction or Proper Orthogonal Decomposition approaches).

Retrieved from "http://scripts.mit.edu/~mor/wiki/index.php?title=Nonlinear_Methods"
Nonlinear Methods