I’ve become really interested in the parallelization of different numerical analysis computations. Sure, it makes the computations faster, but exactly how much faster?

Let’s take the simple example of matrix multiplication. Visualize matrix multiplication as a cube: matrix A and B are placed on orthogonal faces of the cube and the resulting matrix C comes from the final orthogonal face. You can think of the product of A(0,0) and B(0,0) as a corner piece of the cube, the product of A(0,1) and B(1,0) as a side piece of the cube, etc. In this way, you arrive at a 3D cube of products. All that’s left to be done is sum (therefore “flatten”) the cube orthogonally to side C. Viola! the matrix multiplication is solved. While naïve matrix multiplication has O(n^3) time complexity, this algorithm (when parallelized over many machines) has complexity of O(logn).

Parallelizing computation can do amazing things for Gaussian Elimination too. Once again a O(n^3) operation, parallel Gaussian elimination using scaled rank-one updates (described here) Allows you to compute LU factorization in best case scenario O(n).

Interested in learning more? Purdue has an awful lot to say on the subject.