Sketch-based Dynamic Illustration of Fluid Systems

Here is a nice video of sketch based visualization tool of fluid systems. I'm quite amazed by the complexity of the systems that can be modeled that way, and I find the graph version very practical.
It's a nice idea to have a rough idea of your subsystem connectivity, specially when the model is a mess of tubes, valves and containers. I like that !
 Source

Spanning Trees and Direct Solvers

This blog entry will be entirely dedicated to a subject that absorbed me for more than one year: support graph preconditioners. When one have to solve say a laplacian equation on a mesh the numerical discretization  the problem to solve is generally of the form Ax=b, where A is a sparse matrix with many zero entries. More importantly the non-zero entries have a pattern direclty inherited from the mesh connectivity. For linear elements, (i,j) entry is non void if and only if there is an edge between node i and node j (what's cool with the laplacian is that a node is a degree of freedom).

So, as long as the mesh has a moderate connectivity pattern, the matrix inherits  that pattern and is therefore relatively sparse. If you factorize your matrix with a direct solver then the work your computer has to do is directly linked to the connectivity of the underlying mesh. For instance if the underlying mesh is a tree, then the complexity of the direct solver will be linear with respect to the number of nodes in the tree. Not bad.

If your graph is planar (like in the 4-color theorem), then complexity is proportional to the number of node at power 3/2. Not linear, but almost.

 So trees are provably the easiest graph (or mesh, who care) to factorize because they have very low (linear) complexity. The idea of support graph preconditioners is to exploit that fact and construct a approximation of the original matrix which underlying graph resembles as much as possible to a tree.
For a laplacian matrix, it is possible to construct such approximation by considering a minimum spanning tree of the mesh. Of course, it is not as easy as that! To get an efficient preconditioner one have to do something on the approximation, generally adding few additional edges in the spanning tree to reduce the condition number of the preconditioned system (see [3] for instance).

I think it's funny to see that my current work to make solvers faster is very similar to the child game of reconnecting a set of points without lifting the pen and without passing two times on the same edge.

A regular mesh...

... and one of its spanning trees !

However we can talk about the (undirected) graph of a matrix only for particular matrices, like laplacian matrices which are symmetric positive definite matrices with positives entries on the diagonal and only negative entries on the extra-diagonal. In that particular case, we have a isomorphism between the weighted undirected graph and its matrix, but that is a rather technical footnote.

References:
[1] Dan Spielman website (here) have a wonderful talk by him (here)
[2] Bruce Hendrickson webpage (here)
[3] Doron Chen and Sivan Toledo: Vaidya's preconditioners: Implementation and experimental study

Quote of the day...

« Beauty is in the eye of the beer holder »

Copyrighting Algorithms

Each morning, as soon as I arrive in front of my computer, I generally spend a couple of minutes browsing articles of the day on arxiv.org, in particular in the "Numerical Analysis" section (and sometimes on Computational Physic, but that's when I'm in tramping mode). This systematically browsing might look a bit fastidious, but I like to have an large overview of the newest developpements.

In that topic I came across an article named "General Complex Polynomial Root Solver and Its Further Optimization for Binary Microlenses" which has a very interesting appendix (B, page 20) about the utility of patenting algorithms, in particular the discussion stands on the classical book "Numerical Recipes". In fact the author happened to write this article because they needed a different method to compute roots of complex polynomials than the one proposed in the NR book, because of copyright violation. So in some sense, they argue that "copyright and patent law are stimulating intellectual innovation".

But they point out a more general problem about the reluctancy of researchers to release publicly their research code, in particular for Intellectual Property concerns which poses an other problem: reproductability of [numerical] experiments, which is at heart of the scientific method. I thought that was interesting, so I decided to have a post on that topic.

Moreover, the cite the four page article "Practices in Code Discoverability". The title says it all.

Alexandre's post-it dodecahedron

This magnifical (I had english lessons with Sarkozy) sculpture is the artwork of one of my co-worker, Alexandre.

He got the blueprint from here:

http://www.youtube.com/watch?v=vjOOhemquss

Think it's better than post-it war!
http://www.postitwar.com/page/2

Ocean's beauties

from:
www.fubiz.net/2011/04/06/underwater-experiments/

Why Thinking is important

This week I went to the dentist for a routine check-up. By inspecting his waiting room I should have guessed that my dentist was a Jeovah witness. The book questioning the existence of pardise should have warned me.

After a while the dentist came in and I sat in the scary chair with pipes and syringes all over. I looked at my wisdom teeth that I should remove because there is no place left for them in my mouth. I mean really no place, one is pushing against my jaw and it make a terrible infection. The dentist began to explain me that I should open my mind, that I should make some work upon myself and give a place to those teeth, that they were here for a REASON. It was not a matter of surgery, just a matter of faith and self opening to the world. Seeing that I was more and more sceptical, he mistakingly took the example of homepathy to explain me that OTHER WAYS exist. "Yeah, I replied, I know that. It's the placebo effect. But it work only if you believe it". At that point he finally understsood that I would not be convinced by his weak arguments, and he said that I should pay him. Which I did.

Wow, I am happy that dentist is not a oncologist !


I am not against faith for itself, eventhough I'm not a believer. At all. But at some point, believing should not prevent people to think!