Credit: istock Note: Most people don’t want to be the uncool one to raise their hand and ask a question, but in many cases we really should. These occasional “Raise Your Hand and Ask” posts highlight cool buzzwords you may have heard. My aim isn’t just to explain what they mean (that you can look up), but also why they matter. I have one purpose in this blog: to define the term “solvers” when used in reference to a math library and provide some ideas about why these things are interesting. Along the way, I’ll explain some of the various types of solvers as well. There are many mathematical libraries that include solvers in the routines they offer. These are highly valued by scientists and engineers because they solve for unknowns in systems of equations. Story problems from algebra class—on steroids I’m sure you remember story problems like this one: James is going to make three shelves for his daughter. He has a length of wood that is 12 feet long. He wants the top shelf to be six inches shorter than the middle shelf, and the bottom shelf to be eight inches shorter than twice the length of the top shelf. How long should each shelf be if he can use the entire 12 feet of wood (ignoring the 1/8 inch that the saw removes with each cut)? We can create a set of equations: TOP = MIDDLE – 6 BOTTOM = (2 * TOP) – 8 TOP + MIDDLE + BOTTOM = 144 In school, we learned “substitution methods” in algebra classes to solve these. But with computers, we simply write out the equations and let the computer do the work. We do that using matrix algebra, which is a fancy way of saying we pose the problem in a set of equations. The matrices to use to represent the prior equations will look like this: matrices The first matrix holds the coefficients; the second matrix is the variables; and the third matrix is the answer when we multiply the first by the second. (It’s our system of equations in a matrix form.) It turns out the answer, as any solver could tell us, is: TOP = 36.5 inches; MIDDLE = 42.5 inches; and BOTTOM = 65 inches. (I found this nifty website that will solve a set of equations if you want to play with it.) If we want to deal with the saw cut (two cuts reduce the total size by a quarter of an inch), then all we do is change the 144 to 143.75 and run the solver again. Real-world problems are often expressed with complex systems of equations with hundreds, thousands, or millions of equations. That’s when solvers become really interesting. Non-linear equations? I’ve been focused on systems of linear equations. Linear equations, like those in my shelf example, are simple multiples of the unknowns (variables like TOP). It’s not surprising that there are solvers for non-linear equations as well. Clever programmers have found that solvers can be optimized for particular special cases, such as polynomial equations. Even with linear solvers, it turns out that if you have lots of equations (hundreds or more), most of the numbers in the matrices will be zeroes. That’s because most of the equations will not use every variable. In my shelf example, this was the case with two out of three of my equations. Lots of equations + lots of memory = a headache When you create a lot of equations, the matrices get quite large. This uses up a lot of memory. Big systems of equations can easily be larger than memory. Out-of-core solvers recognize this and optimize to operate on problems that are larger than memory. Such solvers trade off doing extra computations to avoid moving data in and out of memory more often. When everything fits in memory, it’s easier for the solver because it can compute on any matrix data at any time without worrying if it is currently in memory. There is another clever solution called sparse matrices. When we have lots of equations, that easily can mean lots of zeroes. It might be possible that the non-zeroes can be organized to be a band of numbers. That’s a special case, and so are other organizations of zeroes and non-zeroes. The general case is called sparse matrix. We use sparse matrices when we accept that most of the coefficients are zeroes. The resulting representation can be dramatically smaller, but the solvers become more complex because they have to deal with a complex representation of the data instead of a simple array. LAPACK (and ScaLAPACK) The most famous library that includes routines for solving systems of linear equations, and much more, is LAPACK. A version that takes advantage of clusters/supercomputers is called ScaLAPACK. Many computer vendors supply optimized versions of LAPACK/ScaLAPACK for their systems. We can link in their optimized version, often without any changes to our code. The longest lived and most popular is probably Intel® Math Kernel Library, recognized as the best overall x86 (and x86-64) optimized math library. It supports LAPACK and ScaLAPACK solvers and more. Solvers: an important toolkit item I’ve only scratched the surface, because solvers have been studied and optimized for decades. The concept of handing a computer a set of equations, and letting it solve them, is as old as computers. In fact, that was the task that computers were busy doing back when computers meant people and only later came to mean that fancy new IBM 7090 mainframe. Of course, you know that already if you’ve seen the movie Hidden Figures. Click here to download your free 30-day trial of Intel Parallel Studio XE Software Development