search

google-research / FirstOrderLp.jl

Experimental first-order solvers for linear and quadratic programming.
Apache License 2.0
103 stars 19 forks source link

Update preprocess.jl to fix the slow diagonal scaling #119

Closed haihaolu closed 1 year ago

haihaolu commented 1 year ago

Fixes #118

The reason for this comes from the fact that Diagonal(.) * matrix creates a dense matrix. This is fixed by using sparse(Diagonal(.)).

dapplegate commented 1 year ago

These are overkill and inefficient. The problem is not that Diagonal Sparse = Dense, but rather the special case of Diagonal Sparse Diagonal. Merely putting ()s around the two occurrences of that expression (i.e., (Diagonal Sparse) * Diagonal) solves the problem, and doesn't introduce the inefficiency of converting a diagonal matrix to a sparse one.

haihaolu commented 1 year ago

Ok. I just pushed with (Diagonal Sparse) Diagonal. This was quite unexpected to me when I first saw the issue.

On Nov 3, 2023, at 2:11 PM, David Applegate @.***> wrote:

These are overkill and inefficient. The problem is not that Diagonal Sparse = Dense, but rather the special case of Diagonal Sparse Diagonal. Merely putting ()s around the two occurrences of that expression (i.e., (Diagonal Sparse) * Diagonal) solves the problem, and doesn't introduce the inefficiency of converting a diagonal matrix to a sparse one.

— Reply to this email directly, view it on GitHub https://github.com/google-research/FirstOrderLp.jl/pull/119#issuecomment-1792966855, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFJGFZSLIRLUS5R6RRP25GLYCU6W3AVCNFSM6AAAAAA64TF2A2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTOOJSHE3DMOBVGU. You are receiving this because you authored the thread.

dapplegate commented 1 year ago

I agree. It was so unexpected I spent some time digging into it, which is how I discovered that it was (somehow) the 3-way product rather than just Diagonal * Sparse.

I see that the Format check failed. I suspect that's because the ()s change the indentation so the julia formatter needs to be rerun.

haihaolu commented 1 year ago

I reran the formatter and just pushed it. PTAL.

It is unclear to me what the benefits of making the 3-way product differ from the one with parenthesis are...

On Nov 3, 2023, at 3:21 PM, David Applegate @.***> wrote:

I agree. It was so unexpected I spent some time digging into it, which is how I discovered that it was (somehow) the 3-way product rather than just Diagonal * Sparse.

I see that the Format check failed. I suspect that's because the ()s change the indentation so the julia formatter needs to be rerun.

— Reply to this email directly, view it on GitHub https://github.com/google-research/FirstOrderLp.jl/pull/119#issuecomment-1793048170, or unsubscribe https://github.com/notifications/unsubscribe-auth/AFJGFZXAN6V7MKG645ZHKHDYCVG4FAVCNFSM6AAAAAA64TF2A2VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTOOJTGA2DQMJXGA. You are receiving this because you authored the thread.

dapplegate commented 1 year ago

It seems like a bug in Julia's diagonal or sparse matrix to me. My guess is that somehow with D S D they're forming an intermediate expression so that they can fold the operations together, or perhaps just choose (D S) D or D (S D) based on dimensions. But that intermediate expression doesn't understand SparseMatrix so it does the dense operation. Explicitly putting in the ()s forces it to resolve that intermediate expression so it does two Sparse * Diagonal operations instead.