Parallelizing Newton-method in solving non-linear systems

Question

Circuit simulation software based on SPICE (such as ngspice) uses Newton-Raphson method to solve non-linear system of equations which model circuits containing non-linear elements such as diodes or MOSFET transistors. In each iteration of Newton-method, most of the time is spent on the following two parts:

• device model evaluation: load the sparse matrix $A$ and rhs $b$ of $Ax=b$ with appropriate values according to the current operating point of the circuit.
• matrix solving: solve $Ax=b$

To speed up the simulation, efforts has been put in parallelizing both parts above, as the literature shows.

Some days a ago, an idea came across to me to speed up the simulation in a coarse-grained fashion, but I am not sure whether or not this is a viable idea or if there were studies/implementations of it already. Let me explain below what's in my mind, and please give advice or indications. Many thanks!

The idea is simple (based on the assumption that many computational resource are available): at each iteration, we try multiple ($N$) candidate solutions in parallel, i.e., $N$ version of $Ax=b$ is loaded/solved in parallel; if none converges, we choose the "best" one from $N$ solutions (somehow, e.g., simply using Euclidean distance betw. candidate and solution as criteria) for the next iteration. again, the next iteration generates $N$ candidate solutions based on the chosen one from the previous iteration (for example, simply choose different step sizes in the direction of $\delta x$), and carry on the process, until it converges or max iterations reached.

The hope is that:

• as we try $N$ candidates at each iteration, the number of iteration to reach convergence will most likely to decrease, thus speed up simulation.
• as we try more candidates, the solution may be a little bit more "global" then local solutions obtained from Newton method.

The following briefly depict the idea above:

Answer 1

It is a very interesting idea and it actually exists. The Newton method is an algorithm utilized to solve the system of nonlinear equations $\textbf{F}(\textbf{x})=\textbf{0}$, where each component of the vector function $\textbf{F}$ is

$$ f_1(\textbf{x})=f_1(x_1,x_2,\dots,x_n)=0\\ f_2(\textbf{x})=f_1(x_1,x_2,\dots,x_n)=0\\ \vdots\\ f_n(\textbf{x})=f_1(x_1,x_2,\dots,x_n)=0\\ $$

Another class of algorithms utilized to solve this system of equations is the use of optmization algorithms to obtain the minimum for a multivariable function of the form $g=\mathbb{R}^n\rightarrow\mathbb{R}$. The conection between both problems appears when we notice that, when defining a function $g$ as

$$ g(x_1,x_2,\dots,x_n)=\sum_{i=1}^n[f_i(x_1,x_2,\dots,x_n)]^2 $$

then the solution $\textbf{x}^*$ of the system of equations is precisely the point where the function has the minimal value $0$. Henceforth, you can work with both the system of equations $\textbf{F}$ (Newton-Raphson and related algorithms) or the function $g$ (multivariable optimization algorithms). There is a lot of material on Unconstrained Multivariate Optimization.

The idea you had about using random numbers to look for the solution of the system already exists. It is part of broader class of optimization algorithms known as Evolutionary algorithms.

To cite two methods, there is the genetic algorithm (GA) and the particle swarm optimization (PSO). Given an initial random distribution of the variables, each algorithm will use a different method to obtain sucessive approximations until the optimum is achieved. As you noticed, "the best solution" is the one that minimizes $g$ or, hopefully, makes $g=0$.