Make Gauss-Seidel great again! The art of unrolling

Two posts in one week! You guys are in for a treat!

This time, we’ll explore how we can use the open-source code analyzer osaca to dissect our Jacobi and textbook Gauss-Seidel kernels and understand why the latter is so slow despite the math saying its should converge in half as many iterations as Jacobi: critical path, loop carried dependencies, port pressure, and the likes. Then, we’ll see how we can use algebraic manipulations and loop unrolling to recover Gauss-Seidel’s convergence advantage without sacrificing the hardware efficiency of Jacobi. Here is the link to the blog post.

Big thank you to @ivanpribec for putting osaca under my radar as well as showing the unrolled Gauss-Seidel kernel.

@rsci : As you had correctly pinpointed last week, most of the Jacobi kernel’s performance comes from ILP. Vectorization gives you an extra speed-up but it really is just the cherry on top.

12 Likes

“Like” deserved, even if it were only for the humorous title and the artwork of your blog post. :grinning_face_with_smiling_eyes:

“Making Gauss-Seidel great again” is no small feat, as it gives much better smoothing (and hence ultimately much faster convergence) rates than Jacobi in multigrid methods.

Glad you liked it :smiley:

I’ve been debating how far I should drag along this series on Jacobi and Gauss-Seidel, and whether multigrid should be part of it or eventually have its own dedicated series. In the end, here is a peak into what I set out to do:

  • Post 4: Red and Black Gauss-Seidel to restore the embarrassingly parallel capabilities of Jacobi (although it is an ordering very specific to this matrix, not as general as the loop-unrolling of this post).
  • Post 5: A detour through performance engineering with a roofline analysis of these kernels. I’m not an expert there so I won’t go too deep, but the idea essentially is to give some intuition of what is the limiting resource (in these cases, it is memory bandwith, not compute) and how it can be analyzed.
  • Post 6: Successive Over Relaxation, basically Gauss-Seidel on steroïds.
  • Post 7: How poorly these methods actually scale as you refine the grid, and why that is an issue for large-scale scientific computing problems.
  • Post 8: A brief introduction to multigrid and how these techniques fit in.

I’ll start teaching on Monday, so my publishing schedule will very likely get quite erratic past next week. I have no idea how long it’ll take me to get to multigrid, but hopefully maybe sometime before Christmas. The content may most likely evolve as I start writing, but the general idea is there. At some point, may be next year, I’d like to do something similar with Krylov methods.

11 Likes

@loiseaujc just wanted to say thanks for your posts (they are all super high quality and relevant) and yes, please do all the other posts you planned.

What classes are you teaching?

1 Like

Thanks a lot, that is very nice of you !

This semester, I’ll be teaching:

  • intro to applied linear algebra (essentially following Boyd and Vanderberghe’s book)
  • linear optimal control and reduced-order modeling for fluid dynamics applications
  • intro to convex optimization

As much as I’d like to use Fortran in my teaching, Python is the mandatory language. I still manage to get a couple of students every year to do some of their projects in Fortran though.

1 Like

How do you teach using Python? Are you using Jupyter Lab, or install it locally and how do you do it (Conda, or something else)?

Not very satisfactorily to be honest. Here is the stack at Arts et Métiers where I do most of my teaching:

  • Some sort of system wide Windows virtual machines administered by the IT service.
  • Python, Spyder, and Jupyter are installed via conda along with the standard packages.
  • For non-standard packages, either we have to install them locally but they disappear once the session is closed (and thus have to proceed again next time) or we try to convince IT that they are safe and have pedagogical value (not too hard, but sometime they simply have other things to do and it takes a while before the package gets deployed system wide).

Every now and then, we have some students who prefer to do everything on their own laptop and so it gets a bit easier (after an initial phase of troubleshooting).

I like Python, but I don’t think it is a language really suitable for teaching the nitty gritty details of a large class of algorithms. For other things, no problems, and you can prototype things quite rapidly so fair enough. I’ve already talked quite extensively about my point of view here. But I think the Jacobi vs Gauss-Seidel discussion is a nice example of why. It would take a lot of ninja skills in Python to get Jacobi to run twice as fast as Gauss-Seidel and that has nothing to do with how the computer works but everything with the language itself. Now this is out of the way, let me answer your question properly.

How do I teach using Python ? – Well, it kind of depends on the class I’m teaching. What is common throughout the different classes however is that I provide the handouts/homework both as pdf + .py files for the students willing to use Spyder, as well as a Jupyter notebook. Jupyter notebooks can be really cool, but one thing I dislike for teaching is that you really do have to execute them linearly. Very often, students have to implement the algorithm in one cell, and run the validation/benchmark cases in another one. And if it doesn’t work, many of them make changes to the algorithm cell and re-execute directly the validation one without re-running the algorithm one. And they don’t understand why their fix did not work until they realize “ah, I need to re-execute the cell I’ve just changed”. It is not a very big issue, but it does add quite a bit of friction. In that respect, notebooks like Pluto in Julia, or even marimo in Python, who keep a dependency graph of the cells, do a much better job. They do come with their own limitations though in that every output of a function should be treated as immutable otherwise it screws up the dependency graph which also adds some friction.

Regarding the different classes now.

Intro to applied linear algebra – Most of the students enrolled in this class finished high-school two or three years prior, and they often can write very simple programs in Python or Matlab. The core of the class is not so much about algorithms themselves rather than being able to formulate a practical (yet heavily simplified) engineering problem in a way it can be solved using simple linear algebra techniques. The poster child here is the QR factorization because you need very little math background to implement it (just vectors, dot products and norms), so does the backward substitution for solving the upper triangular system. When introducing the algorithm, we do have a small discussion about flops (how many flops for a dot product, for a vector addition, etc?) so that they at least get some intuition about computational complexity. They do have to implement this algorithm themselves at least once, but then we just use scipy.linalg.qr and scipy.linalg.solve_triangular.

Mathematically, the two main types of problems/algorithms we discuss are kmeans and equality-constrained convex quadratic programs (like least-squares or least-norms). There are a surprisingly large number of engineering applications you can tackle with only this: linear optimal control, Kalman filters, certain types of linear system identification techniques, curve fitting, clustering for topic discovery in document analysis, simplified forms of robust linear programs for resource allocation, signal processing and smoothing, etc. So the aim of the course is not so much to teach how to do these optimally every time, but more like “look, all of these different problems can somehow but put in the approximately same form, and if you know QR you can get a working solution”. It may not be the exact formulation, nor the optimal way to solve the problem, but at least it works and so I see it like giving them some street-fighting skills. Also, because it is directly applied to problems they may know or understand the practical relevance of, it gives them some more incentive and motivation to see why they may need at least a working understanding of numerical linear algebra.

Linear optimal control and reduced-order modelling – This more of a math-oriented class, still with quite a lot of linear algebra. It is part of a master program in fluid dynamics, and PhD students can also enroll. Convex quadratic programming and SVD are the two main stars of the show. But because the material is quite dense and we only have 30 hours or so in total, we don’t do any programming session in class, nor discuss the details of the linear algebra algorithms themselves, more like a high-level overview of how to compute things like balanced truncation, or value iteration if that rings any bells. Students do have a project to do by the end of the class, and most of them use Jupyter notebooks for the reporting even though I know many of them actually do the development part using Spyder.

Intro to convex optimization – It is a pretty short course (only 12 hours in class, 18 hours in the computer lab divided in 6 sessions) intended for 2nd year Mechanical Engineering students. Until last year, the class was very algorithm-oriented. Students had to implement gradient descent, conjugate gradient, as well as Newton and Quasi-Newton methods. But also because of the students have little experience with programming, we had to stick to fairly simple problems (up to a dozen variables maybe) and so it was hard to have really interesting problems or show the practical difference between Newton and quasi-Newton. Most of the students there were using Jupyter. I am now fully in charge of this class and was given the opportunity to change the whole syllabus so I am currently leaning toward something like the applied linalg class: focus more on the problem formulation and use specialized libraries like cvxpy to abstract away the algorithmic parts so that we can focus on more concrete and illustrative problems. Students will still have to implement a couple of algorithms themselves to get the gist of it but it’ll no longer be the main subject.

All in all, I think I could make a much better use of Jupyter or even Python to have more interactivity in class than what I’m doing now. But given the types of students I have (not particularly numerical methods oriented nor computationally literate), I think I’m facing two more important problems than “how to best use Python in class”:

  1. Most of the students don’t see the point in learning this stuff because “hey, it’s already available in numpy or scipy so why should I bother learning how to implement this stuff?”. Also many of them want to become CFD engineers in companies like Airbus or SAFRAN, and they are like “instead of focusing on the maths of PDE or numerical methods, shouldn’t we actually do more large-scale simulations with ANSYS or StarCCM+ because this is what the market is using and I want to be operational with these tools?” I think both questions are valid from a student perspective and I haven’t really been able to come up with a satisfying answer. The best I can do is something along the lines of “well, being computationally literate can only make you a better engineer” but they don’t really get why until they actually face a major problem in their simulations.

  2. The other thing is the widespread usage of LLM for anything. And students have a very good natural understanding of physics: they’ll follow the path of least action. And so, here, I’m actually facing two related problems/questions:

    a. “Why should I bother learning this stuff if I can prompt an LLM and get a better solution that I could come up with, and faster? Shouldn’t we actually learn better prompt engineering techniques instead?” Again, very sensible question from a student perspective. And again, not a very satisfactory answer in my opinion: well, if the shit hits the fan, you better know the math and the numerics to understand what went wrong. True enoug, but LLM are getting better and better at this. The other answer is well if an LLM can do this, and if every students learn how to prompt the LLM, what will be your added-value to the company that employs you? Why would they bother keeping you around if you are that replacable? This usually triggers them a bit, but as a teacher and mathematician, definitely not satisfactory either.

    b. Because these are intro classes, the problems in the set are fairly simple precisely because students should be able to do it on their own. But because the problems are simple, they can just copy-paste into whatever LLM they use and get a working solution with no effort. And that is very hard on me because I have no idea how to actually test what they’ve learned or not. There is also a very nice essay by Lorena Barba (here) about how using LLM often give the students the illusion of competence.

That’s a pretty long answer, I realize I went a bit off road so sorry about that >.<

1 Like

There is a quote I’ve seen attributed to different people that I agree with (somewhat) that goes something like (paraphrasing)

“If you can’t program it then you don’t really understand it”

I’ve found over the years that I get a greater insight into the underlying math and physics if I can see it expressed in code but that’s probably just how my brain works.

2 Likes

@loiseaujc thank you for this excellent answer! I could spend hours discussing, but I’ll just say quickly that I think LFortran + Jupyter, lately including JupyterLite (so that it runs in the browser on a statically-hosted webiste, no installation needed) might be a great solution.

Regarding why program at all when we have AI:

I would say AI actually allowed me to reimplement from scratch many things that I had to use libraries for before. An example from just this month: PNG and GIF encoder and decoder (in Fortran!) using AI, there is no way I would have time to do that by hand, but using AI and studying the sources, it’s actually not complicated at all, and I have a much better understanding of the details than I would have otherwise. Of course, if I did it by hand, I would understand it even better, but I don’t have time for that.

But even before AI, I always liked to reimplement things from scratch, it’s the only way to understand them for me. But it’s sometimes hard to justify the time (but even before AI often in the long run it would pay off to reimplement from scratch, I have done that many times in my career). But with AI it’s actually quite easy to reimplement many things from scratch.

I’ve played around a bit with LFortran and the REPL. This is so cool! I really wish I could use Fortran in the classroom, unfortunately this is the one thing I have no control over. Part of the requirements for the different classes are overseen by the Commission des titres d’ingénieurs (CTI), and (as far as I understood) Python is pretty hot on the list, understandably so. A bit more freedom in the Master Program though, and I know one of my colleagues still uses Fortran quite extensively in their Advanced numerical methods for compressible fluid dynamics. I need to catch up with him and spread the good work of LFortran :slight_smile:

I couldn’t agree more with what you said (@certik and @rwmsu). I also get a much better understanding of numerous algorithms by implementing them myself. This has always been the case, at least since my Uni years. But I’d say being able to come-up with a somewhat performing implementation (Fortran good practices + high-level understanding of how compilers do their job) has been very helpful recently, not only for my HPC simulations obviously, but also for computational exploration of certain problems to get some intuition rapidly before trying to formalize things mathematically. What I have in mind here is something as simple as a few pure functions with a handful of do concurrent loops to run an embarrassingly parallel parametric study for some 3-DOF ODEs and get some physical intuition of what the system’s properties are. I think this could be just as valuable to students as anything else. And AI/LLM have been helpful here are as well and saved me a tone of time. But I believe they have been helpful (at least to me) precisely because I had a pretty good idea of what the implementation would look like, what would the bottleneck be, and had a good sense for how it could be resolved.

And I think this is one major difference between you, I, pretty much anyone of this forum and the students: we already got (hopefully) pretty solid foundations in both math and programming Thanks to this, we can skim through LLM-written code (possibly written with our own specifications), get the logic rapidly, discard any boiler plate code (variable declaration, allocation, etc), and focus directly on the handful of critical operations to understand what is going on. In contrast, students with shaky foundations will often take the generated code at face value, not only because they’ve heard everywhere that AI was good for everything, but also because (in my opinion, but I may be wrong) they are often utterly incapable of mapping some simple abstract-ish mathematical concepts into operational code. I think that, for these students (which happen to form a larger and larger fraction of the cohorts I see), using AI too early for teaching/learning scientific computing is doing them a big disservice.

2 Likes