Message Boards Message Boards

Does the Solve function for simultaneous equations benefit from HPC / GPUs?

Posted 2 years ago

Hello, I use the Solve function to find solutions for systems of simultaneous equations with dozens or hundreds of equations and variables. This is successful though very slow (weeks) on a conventional single processor multi-core system. I am considering moving these problems to AWS with GPU support, with thousands of CUDA cores using one or more NVIDIA A100 GPUs. My question is, does the availability of such massive parallel computational capacity vastly improve execution time of the Solve function, realizing that while some computational problems can benefit greatly from a parallel computing environment, others can not, due to the inherent nature of the algorithms. Further, in the case of the Solve function, a multitude of methods are used internally depending on the nature of the system of equations, and it might be the case that some of these methods can benefit, while other might not. In my case, the equations are polynomials with terms that involve the product of a coefficient and various combinations of the system variables raised to different powers, and nothing more complex than that, in case that might lend insight to the methods Solve might use on these problems. Any help or insight is greatly appreciated. Thank you!

POSTED BY: Roger Smith
4 Replies

In the situation you describe, Solve will likely need to compute a Groebner basis. This is not parallelized. For large systems of equations it might, however, paralyze your CPU.

POSTED BY: Daniel Lichtblau
Posted 2 years ago

Thanks very much Daniel for your reply. If Solve is not accelerated in a parallel computing environment, does that also mean that running it on a single multi-core processor with a greater number of cores would also not reduce execution time, and that the only way to reduce execution time is to use a faster processor?

Also, re the Groebner basis, I have noted your published work on that topic. I am only generally familiar with it and its application in solving simultaneous equations, but I gather from your reply that the computation of a Groebner basis is not amenable to parallelization. In addition to my earlier description of the type of equations I am working with (polynomials with terms consisting of a coefficient and multiple variables involving only multiplication), I will also note that I am interested in numeric, not symbolic solutions, and further, that all variable values are integers. Also, in some of these systems all of the variables in the polynomial terms are only to the first power. I don't know if that makes a difference with regard to the need to generate a Groebner basis by Solve or if other methods might be used internally that are amenable to parallelization. Is there a way to ascertain which solution methods are being used by Solve in a particular instance?

Also, in some earlier work on smaller sets of these equations, I have successfully used the simple substitution method to obtain solutions using custom algorithms. Being familiar with that method, I can see that parallelization is possible, since different processors can be working on different substitutions. Can Mathematica be instructed to try that method? Is there a function for it? If so, can that function / method make use of multiple processors and/or GPUs? Or is it the case that none of the computer algebra functions in Mathematica are able to benefit from multi-processor / multi-core computational resources because the computational steps can only be executed sequentially? Thanks in advance to Daniel and to all for your assistance!

POSTED BY: Roger Smith

With the refinements to the scenario there are further possibilities. First let me address parallelization in the general case. There are ways in which a Groebner basis routine (GB) can benefit. Some are in a sense speculative (try a few things, run with whatever returns first) and some have more to do with deep-down internals e.g. if linear algebra is being used under the hood. Given that GroebnerBasis will use exact arithmetic in the setting described, even if the Groebner walk gets used, the linear algebra will not likely use parallelization (and if it does, I doubt it will help much).

Next, in the case where some or all equations are linear, I believe Solve and NSolve will in effect use substitution to reduce the number of equations and variables. I do not know offhand if this requires an equation be linear in all variables though. If the entire set is linear, Solve will recognize this and use linear algebra exclusively, so no GB computation.

If the system is exactly determined, that is, finitely many solutions, and numeric solutions suffice, then NSolve or FindRoot become viable alternatives to Solve. The former can be directed to use a sparse homotopy method (I forget the option setting that enforces this). This method uses path tracking for each solution. A benefit is that this step is parallelized across CPUs. That stated, if your system is massive, methods that attempt to find all solutions might fail to complete in reasonable time. If you can live with individual solutions, FindRoot is a good bet.

POSTED BY: Daniel Lichtblau
Posted 2 years ago

Thank you again Daniel! I will apply the methods you discuss, study these further, and do some experimentation. I truly appreciate the level of detail of your replies, and the time you spent preparing them! Take care.

POSTED BY: Roger Smith
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract