Description of how to streamline solvers

[aiueogawa]

Hi, @yaksoy Thank you for your great paper!

I have some questions about ways to solve problems more efficiently. I think your prototype implementation roughly includes 4 processes excluding a feature extractor and their respective computational costs for a single 640x480 image follow:

1. calculation of Laplacian matrix L from affinities (~1 sec)
2. calculation of eigenvectors of L (~ 1 min)
3. solving a constrained sparsification problem (~3 mins)
4. solving a relaxed sparsification problem (~30 secs)

By the way, you say in paper,

The efficiency of our method can be optimized in several ways, such as multi-scale solvers, but an efficient implementation of linear solvers and eigendecomposition lies beyond the scope of our paper.

There seems to be 3 ways to make the execution time shorter, multi-scale solver, more efficient linear solvers and eigendecomposition.

Questions:

1. However, which processes do they correspond to?
2. What is multi-scale solver?
3. Can I make the most heavy process (process 3) faster?