3
$\begingroup$

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:

Finding OP

Finding OP continued

$\endgroup$
  • $\begingroup$ It's an interesting idea! I am not sure if there is a performance increase to be gained. Let's say you have fixed computational resources, then any computational power you take away from the newton iteration has to be -better- invested than in the newton iteration. Most of the times we are memory bound, meaning that the memory op's take up most of the time. Another iteration does not hurt too much, contrary to allocating and trying more candidates. IHow would you choose the candidates? $\endgroup$ – MPIchael Oct 9 at 7:57
  • $\begingroup$ @MPIchael I am assuming that all workers (each works on one candidate at a time) are separate entities (e.g., hardware cores) run in parallel, and memory for matrix are allocated once as the circuit topology does not change during the iteration. I am not sure if memory is an issue, it depends on sparsity as well of number of workers. As for choosing candidates, the simplest way in my mind is using Euclidean distance as criteria, i.e., a worker gets a $x$ as input and returns a $\hat x$ as output, then may be a smaller $|\hat x - x|$ suggest that this worker is closer to the final solution? $\endgroup$ – bruin Oct 9 at 8:16
  • $\begingroup$ Hmm. Its an interesting idea, but i'm not sure about performance. If you throw all your power into newton iteration, and its a sparse matrix, you can approach linear increase in speed (I think). Same might hold true for using computing power to come up with candidates. If performance is bound to the number of candidates, then it might also speed up linearly. The question now is, which of these methods might hold a better speedup. Maybe you can work out the computational order of the proposed method. Is it O(N), O(N²) etc? $\endgroup$ – MPIchael Oct 9 at 8:31
  • $\begingroup$ Not sure if I understand you correctly. My understanding of the speedup issue is that, even you have plenty of resources (cpu and ram), with conventional Newton method, it's hard to leverage the resources during the process. The speed up approaches I am aware of so far are parallelizing the work (e.g., matrix solving) inside each iteration, i.e., speed up each iteration without change the number of total iterations (required for a given problem). My idea is kind of orthogonal to it, i.e., instead of speed up each iteration, try to decrease the number of iterations. $\endgroup$ – bruin Oct 9 at 9:08
  • $\begingroup$ 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})$. (too long for comentary, will post an answer) $\endgroup$ – Thales Oct 9 at 9:57
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks for your answer and links, Thales! $\endgroup$ – bruin Oct 10 at 2:03
  • $\begingroup$ What about the local minima introduced? $\endgroup$ – nicoguaro Oct 10 at 3:37
  • $\begingroup$ As a general comment, since in this particular case of finding the solution to the nonlinear system of equations, you can check whether $g$ is $0$ or not. If so, you have found the solution. Otherwise, you are on a local minimum. You can change your initial conditions and rerun the code. $\endgroup$ – Thales Oct 10 at 10:51
  • $\begingroup$ In the particular case of the two methods presented, the GA algorithm have a tendency to converge to a local minimum. This can be alleviated by replacing part of the population with randomly generated individuals - a strategy close to changing the initial conditions, but done programatically. $\endgroup$ – Thales Oct 10 at 10:54
  • $\begingroup$ For the particular case of the PSO, adaptative mechanisms can be introduced. Adaptive particle swarm optimization (APSO) features better search efficiency than standard PSO and can perform global search over the entire search space with a higher convergence speed. APSO can act on the globally best particle to jump out of the likely local optima, with the cost of introducing new parameters to the algorithm. $\endgroup$ – Thales Oct 10 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.