Possible performance improvement?
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 35/100
- issue の種類
- 機能追加
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 技術スタック
- julia
- 領域
- performance
調査の方向性
src/NonLinearProgram/NonLinearProgram.jl の ForwCache と Δs の計算付近から始め、次に src/NonLinearProgram/nlp_utilities.jl の _compute_sensitivity と _compute_derivatives_no_relax を追ってください。forward および reverse differentiation について、既存の K\N solve と lazy な vector-RHS solve を比較してください。Jacobian-vector の結果を維持しながら、不要な線形システム処理とメモリを削減できれば完了です。
索引モデルが issue の本文から書いたものです。
説明
following an initially-unrelated discussion with @andrewrosemberg
I think there might be room for (substantial 🤔🤞) performance improvements in the NonLinearProgram code.
Note: what I write below might apply to other classes of problems, I only checked the nonlinear code so far.
TLDR: I think we can replace {a lot of linear system solves} with {a single linear system solve} during forward/reverse diff
Medium-long explanation:
Forward/reverse diff compute Jacobian-vector products of the form J*v or J'*v, and the Jacobian J is of the form K\N, where K, N are matrices. Currently, to obtain w=J*v, we solve KJ = N (matrix RHS), then compute J*v. I believe we can instead compute w = Jv by solving Kw = (Nv), which requires a single linear system solve (with vector RHS).
Why it matters for the ACOPF example I work with, on a 300-bus case with loads as parameters, K has size 13k x 13k, and N is 13k x 200. Replacing K\N with K\(Nv) potentially yields a 200x reduction in memory and time.
Complete thought process and stack traversing.
I'm focusing on forward diff for the sake of example, same remarks apply to reverse diff
- Forward diff returns primal/dual sensitivities in a
ForwCachestructure here:
https://github.com/jump-dev/DiffOpt.jl/blob/df4a7dcee059ee048ff620590ff5478d8b2c79cc/src/NonLinearProgram/NonLinearProgram.jl#L534-L537 - These are obtained from a left multiplication with Jacobian here
https://github.com/jump-dev/DiffOpt.jl/blob/df4a7dcee059ee048ff620590ff5478d8b2c79cc/src/NonLinearProgram/NonLinearProgram.jl#L530-L532 - Said Jacobian
Δsis computed by the_compute_sensitivityfunction. Stepping into that call, said jacobian is obtained from_compute_derivatives_no_relax
https://github.com/jump-dev/DiffOpt.jl/blob/df4a7dcee059ee048ff620590ff5478d8b2c79cc/src/NonLinearProgram/nlp_utilities.jl#L457 - which then points us to a linear system solve
https://github.com/jump-dev/DiffOpt.jl/blob/df4a7dcee059ee048ff620590ff5478d8b2c79cc/src/NonLinearProgram/nlp_utilities.jl#L425-L427
The alternative implementation I propose would cache the factorization of K (which seems to already be the case), and lazily compute Jacobian-vector products w=J*v by solving w = K\(Nv). The math would be similar (I think) for Jacobian-transpose-vector products
- 主要言語
- Julia
- スター
- 146
- フォーク
- 21
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
jump-dev/DiffOpt.jl のほかの issue
-
難易度 3/5 1〜2日 初心者へのやさしさ 55/100
jump-dev/DiffOpt.jl#362 · コメント 1 件 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
jump-dev/DiffOpt.jl#358 · コメント 2 件 ·
-
難易度 3/5 1〜2日 初心者へのやさしさ 55/100
jump-dev/DiffOpt.jl#348 ·
-
good first issue
難易度 4/5 3〜5日 初心者へのやさしさ 48/100
jump-dev/DiffOpt.jl#336 · コメント 4 件 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 35/100
jump-dev/DiffOpt.jl#331 · コメント 1 件 ·
jump-dev/DiffOpt.jl の issue をすべて見る
似ている issue
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 73/100
メンテナーはふだん 1 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 76/100
-
documentation model-weights
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
FluxML/Metalhead.jl#311 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
jump-dev/MathOptInterface.jl#3113 ·
メンテナーはふだん 1 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 83/100
JuliaMath/Polynomials.jl#647 ·