Faster, I say! The race for the fastest SDD linear system solver – STOC 2014 Recaps (Part 9)

Look forward to seeing the results on the simulation solver. The connections between SDD solver to matrix exponential.

Not so Great Ideas in Theoretical Computer Science

In the next post in our series of STOC 2014 recaps, Adrian Vladu tells us about some of the latest and greatest in Laplacian and SDD linear system solvers. There’s been a flurry of exciting results in this line of work, so we hope this gets you up to speed.


The Monday morning session was dominated by a nowadays popular topic, symmetric diagonally dominant (SDD) linear system solvers. Richard Peng started by presenting his work with Dan Spielman, the first parallel solver with near linear work and poly-logarithmic depth! This is exciting, since parallel algorithms are used for large scale problems in scientific computing, so this is a result with great practical applications.

The second talk was given by Jakub Pachocki and Shen Chen Xu from CMU, which was a result of merging two papers. The first result is a new type of trees that can be used as…

View original post 1,858 more words

Advertisements

Julia @ Ubuntu 12.04

Julia has some issues when I compiled in Ubuntu 12.04. I modify a little on top of http://ubuntuhandbook.org/index.php/2013/08/install-gcc-4-8-via-ppa-in-ubuntu-12-04-13-04/

1.)  at terminals

sudo add-apt-repository ppa:ubuntu-toolchain-r/test

2.) Then install gcc 4.8,  g++ 4.8, gfortran-4.8

sudo apt-get update; sudo apt-get install gcc-4.8 g++-4.8 gfortran-4.8

3.) Once installed, run following commands one by one to use gcc 4.8 instead of previous version.

sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-4.8 20
sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-4.8 20
sudo update-alternatives --install /usr/bin/gfortran gfortran /usr/bin/gfortran-4.8 20

Besides stiffness problem, the explicit methods are still not better than implicit methods?

Considering the simple dynamical system as follows

{\bf C}{\bf \dot{x}}(t)={\bf G}{\bf }x(t)+{\bf B}{\bf u}(t)

where \bf{C} and \bf{G} are sparse matrices, {\bf u}(t) is a input and \bf{B} is incident matrix which poses {\bf u}(t) in the system.

In my thought, the explicit methods work if there is not \bf{C} on the left hand side,

{\bf \dot{x}}(t)={\bf G}{\bf x}(t)+{\bf B}{\bf u}(t)

e.g. solve it by forward Euler method and ignore the input for simplicity (\bf{\dot{x}}(t)={\bf G}{\bf x}(t))), then

{\bf x}(t+h)={\bf x}(t)+h{\bf G}{\bf x}(t), where h is the discretized time step.

However, when this is not true, the explicit method still need to solve linear system, because

{\bf C}{\bf x}(t+h)={\bf C}{\bf x}(t)+h{\bf G}{\bf x}(t) or say it requires inversion of matrix {\bf x}(t+h)={\bf x}(t)+h{\bf C}^{-1}{\bf G}{\bf x}(t)

Any comments?