omn123

Consider, for example, calculating binomial coefficients mod a large number.

It's not hard to realise that C(n,k+1) = (n-k)C(n,k)/(k+1) is one way to write the binomial coefficients. So if we want to compute C(10^10,50309) mod 10^8, for example, we only ever really need to carry numbers mod 10^8 around. And since (ab) mod c = (a mob c)(b mod c) we can avoid obtaining really large numbers and can safely hold them in unsigned long ints.

Since this problem is counting things, there is mostly like a recurrence-type relationship to it and at each step you would take the result mod N. Many combinatorics problems are like this. Although if you've only done 60 PE problems, then the ones in the 400s somewhat implicitly assume you've done the previous 400 since the ideas do built up.

I've alluded to this in other comments but a lot of the mathematics is linear algebra. As gaius mentions, check out the wikipedia article. There are plenty of linear algebra books out there. Recently I've really enjoyed the book by Meyer which is free although it does get quite advanced and is mostly theorem / proof-style. It's also free so who can complain.

http://matrixanalysis.com/DownloadChapters.html

Here is a link I found yesterday which gets you solving the 2D NS equations.

http://lorenabarba.com/blog/cfd-python-12-steps-to-navier-st...

I've take a quick look through it and it seems pretty good. It introduces many of the most important ideas of solving PDEs. Obviously there are huge tomes on various techniques to solve the Navier-Stokes equations but this link, I think, does a pretty good elementary introduction. A more comprehensive treatment would require a more thorough background in mathematics (e.g. I wrote a 2D NS solver using the vorticity formulation and FFTs but to understand the equivalence requires a greater background).

As for the cool visualisation, I cannot help you. I don't know any fancy graphics programming since I normally use the built-in plotting tools of Python and Matlab.

You are quite correct about stability but I didn't want to get into technical details. And indeed you bring up correctly that such numerical issues mustn’t be treated lightly. I don't do computer graphics and the matrices I deal with are well conditioned such that problems of stability that arise due to linear algebra routines are negligible. In my simulations, instability arises due to the wrong time-stepping scheme, which is a completely different issue.

And good recommendation by Strang. I believe he has some fantastic MIT OpenCourse lectures on numerical linear algebra as well.

Well today I learned. I never knew that. Stupid mathematics and its inconsistent notation.

I'm not implying yours are not unstable, it's just there is a chance it might be. Typically exact formulas exhibit such properties.

LU decomposition is numerically stable, for the most part. You can run into problems with floating point arithmetic if you're not careful. This just has to do with the way you solve the problem. By breaking up the matrix into an upper and lower triangular part and solving the resulting triangular system, you often avoid things like powers or square roots and just reduce everything to basic addition and multiplication which tend to have more stable numerical properties.

As for speed, well in this small case of N=4 there is probably very little speed increase since LU is O(N^{3}), although this can be improved depending on symmetries of the matrix. Maybe for N=5 I might write out the exact formulas but beyond that I would just a LU solver since the amount of code for an LU solver is fairly compact.

But, as you correctly point out, if you are never changing the matrix A then you are probably safe with writing it out this way.

I just come from a numerical fluids background so seeing exact formulas makes me uneasy. And in my work since the number of grid points N tends to be variable so general formulas are not available. Plus I've noticed a lot of programmers tend to not know numerical algorithms. In fairness, I don't blame them. All the numerical computations courses I've taken and TAed are very boring and don't make you do anything fun and numerical analysis has this reputation of being dry. If you actually made them write stuff like a Navier-Stokes solver, you would get them interested.

By the way if you want to learn more about numerical linear algebra, which is the cornerstone of most scientific and high performance computing, I personally enjoy Trefethen and Bau's book. Although it's aimed at a mathematical audience and assumes such.

It is actually linear. a,b,c,d are the unknowns and x1 and x2 are the inputs.

A bit confusing since normally x1,x2 denote the unknowns.

It's worth pointing out that you should rarely, if ever, use exact formulas since there are a lot of problems with numerical stability amongst other things. Often it is faster to just numerically solve the system.

For example, in your case you are solving Ax=b which you can easily solve by a simple LU decomposition. Plus if your A changes, your exact formula is wrong, so using an LU decomposition just makes sense. Plus your code will look way cleaner as well. And way easier to debug.

http://en.wikipedia.org/wiki/LU_decomposition