Saturday, December 18, 2010

CS: The Boogie Woogie Grid

In Lena's Prisoners I asked:

Well if the measurement matrix is not random enough, why aren't you spending all your waking hours making it random ?

One of the ways you can randomize your problem when solving for a field is to provide some randomness in the grid on which the field is being discretized on. Initially, computational and convergence results relied mostly on uniform grids, but in specific fields where that was not enough, adaptive grids production have been the mainstay for the past twenty years. But this is not the path we ought to take, in Finite Element Methods for instance, the goal is to sparsify the stiffness matrix as much as possible through the discretization of derivative operators. The resulting matrix is sparse and any type of randomization of the spatial or time step would make this matrix "weakly" random.   The ideal would be if the randomizing would affect the whole matrix. In order to do that, we have to come back to the assumption that the stiffness matrix ought to be square and sparse in the first place, a central tenet of linear algebra and computational science and engineering. For instance, let us take the example featured in Non uniform grids for PDE in finance where the authors make the choice of using a PDE when in fact in order to have a full matrix, one ought to have an integral form of the same equation.  As soon as the matrix is full because you used the integral form, the non-uniform/random grid makes perfect sense in light of the results obtained in compressive sensing with random measurement matrices. This approach also "solves" the issue of giving some meaning to the test functions used in traditional FEM. I haven't looked around but are there any scripts that produce Mondrian grids like the Boogie Woogie grid shown above ?

No comments: