# Mapping to a computationally less expensive basis when employing Newton's method

I'm looking for advice, or references, for a change of basis to my dependent variables that leads to a less computationally expensive scheme when solving a system of coupled polynomial equations. Below is an explanation of the problem, which will be somewhat involved.

The general idea is this. I have a system of equations I'm solving for the dependent variables $a=(a_1,...,a_N)$, all of them are a function of a parameter $\mu$. That is, my system takes the form ( I will call this method 1)

$$F(a; \mu)=0.$$

For a fixed (prescribed) value of $\mu\in(0,1)$, I solve this system using a Newton-Raphson method (implemented in SUNDIALS), increasing $N$ until my solutions converge to some given precision. For large values of $\mu$, $N$ grows very large and at a certain point becomes very impractical (see my note at the bottom for more about this).

Now, these variables $a_i$ correspond to Fourier coefficients of a physical boundary displacement. In particular, they are Fourier coefficients to two parametric functions $(X(x),Y(x))$, with $X= x+\sum_{n=1}^N a_n \sin n x$, $Y=\sum_{n=1}^N a_n \cos n x$, and $x\in (-\pi,\pi)$.

For a simple example, I have plotted $(X,Y)$, $(x,X(x))$, and $(x,Y(x))$ in black in the figure.

Okay, so there exists another way to formulate this problem, using a different set of variables that leads to a very different set of equations that returns the same information about the boundary displacement. Using ginput in Matlab, I can extract the boundary displacements based on results in the literature that employ this other method (call it method 2), to find a set $(U(x),V(x))$, $(x,U(x))$, and $(x,V(x))$, where the independent variable $x$ is exactly the same as before. These are the red plots in the figure.

Now, we note that $(U,V)$ and $(X,Y)$ give approximately the same plot, but $U$ and $V$ are not nearly as localized in space as $X$ and $Y$. This implies that $U$ and $V$ need much lower spectral resolution than $X$ and $Y$.

This motivates me to look for a change of basis in my original problem, to one that needs lower resolution. In particular, this later approach makes me think that I'm working too hard to get at these solutions, and this becomes particularly apparent as I try to describe the system with higher values of $\mu$.

Now, I realize I should just figure out a mapping between the two methods, but this is very difficult due to the fact that both methods use a series of mappings to get to the final set of equations. So, this information is not available.

My question: Is there any general way, or are there any instances where people have found a way, to do a simple transformation of my variables $a$, to converge for smaller $N$. (I'm not sure if this is the same thing as asking about $preconditioning$ the jacobian of $F$, to allow for more rapid convergence of the Newton-Raphson scheme?). If so, how does one look for this transformation ?

I apologize for the vague question, and please feel free to ask any questions of clarification.

Note: I'm actually solving an ODE with a nontrivial set of coefficients on the highest order derivative, so I'm really solving a system $F(a, t_i)$ for each time step $t_i$. This makes it very important for me to optimize the time taken to solve $F(a)$, as I will do this many, many times.

• Can you give a concrete example? Why are you adding more and more variables? – Bill Barth Feb 4 '15 at 3:31
• @BillBarth I'm adding more variables to converge to the actual solution (which is the case when $N\to \infty$). I could put the explicit equations I'm solving for in here, but it involves a bunch of definitions, and will likely convolute the question even further. – Nick P Feb 4 '15 at 3:55
• What did you end up with ? (Multigrid method in space and time ?) – denis Jun 19 '17 at 12:36