Linear solvers are behind lattice QCD

In my first post I told you about the wonders of lattice QCD, and I explained why we need supercomputing to actually solve problems involving very small particles. I told you about huge machines that can do in one second the same computations a scientist needs thousands of years to complete.

I hope that the post made you fantasize about exploring the subatomic world, but now it is time to get concrete. Yes, because if you recall the title of my project there is something I have not told you about. Just in case you forgot the title here it is: ‘Mixed-precision linear solvers for lattice QCD‘. Wait, what is a mixed-precision linear solvers? Yes, you are right, I did not tell you what a linear solver is at all!

A linear solver is used in many computer simulations to solve a linear system. Linear systems are not difficult at all, when they are small. You probably have solved many of them during high school. Just to refresh you memory, here you have a linear system:

This is a linear system. Is not that bad when it is just two lines, isn’t it? Unfortunately in HPC we have millions or even billions of lines

Solving a linear system means finding the values of the variables involved (in this case, X and Y). Now, there two questions that may arise:

1.  Why are we talking about linear systems at first place? Shouldn’t we talk about lattice QCD, and scientific simulations using High Performance Computing?
2.  These linear systems are way too easy: why do we need supercomputers to solve them?

I will answer the second question first: Linear systems are conceptually simple to understand, but they are usually huge. We can have linear systems with billion lines and billion variables. When we have linear systems of these dimensions, we can’t solve them by hand, and not even using our laptop. We need a supercomputer, but above all we need efficient techniques to solver the system. In other words, we need good linear solvers.

Here it is how it looks likes the matrix representing a linear system in theoretical physics. Fascinating, isn’t it? ( The matrix and the image are taken by http://www.cise.ufl.edu/research/sparse/matrices/)

Now it’s time to answer the first question: what does linear systems have in common with lattice QCD? In lattice QCD simulations it happens quite often to solve a linear system. The reality is that in a standard lattice QCD simulation, most of the time is spent solving large linear systems! In some cases, you can spend 90% of your simulation time solving a linear system and if you consider that lattice QCD simulations use around 20% of computational resources in America, you can easily compute how much time is spent in solving linear systems, and why we need to optimize this procedure.

Additionally, most of scientific and engineering applications, after a little of manipulation, are reduced to the solution of a linear systems. As a consequence, everyone needs linear solvers in HPC!

Fortunately, solving a linear system happens so many times in supercomputing, that efficient solvers are already available and many brilliant scientists are working everyday on making them even more powerful. So, if you have an application that needs to solve a linear system, you don’t have to start from zero: on the contrary you can definitely stand above the giants’ shoulders.

Solving a linear system is just one of the problems that arise in a field called linear algebra or computational linear algebra. Computational linear algebra is little known, but it is everywhere in HPC. Just to make an example, the Google PageRank algorithm is a big linear algebra problem!

Do you know that the Google PageRank algorithm is just a huge linear algebra problem?

(If you want to know more about computational linear algebra, I suggest you this article 10 surprises from numerical linear algebra)

Now you should have a global idea of what I am doing here at the Cyprus Institute, for the PRACE Summer of HPC. I will work on the optimization of a linear solver for lattice QCD simulations. During this weeks I had a taste of complexity in lattice QCD and linear solvers, but I am more motivated than ever! Will I achieve to make lattice QCD simulations faster? We will have the answer quite soon!