Possible performance improvement?
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 35/100
- Issue 类型
- 功能
- 描述清晰度
- 基本清楚
- 活跃度
- 停滞
- 技术栈
- julia
- 领域
- performance
调研方向
从 src/NonLinearProgram/NonLinearProgram.jl 中 ForwCache 和 Δs 计算附近开始，然后跟踪 src/NonLinearProgram/nlp_utilities.jl 中的 _compute_sensitivity 和 _compute_derivatives_no_relax。比较现有的 K\N 求解与用于正向和反向微分的 lazy vector-RHS 求解。在保留 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
- 平均合并
- 1 小时 25 分钟
- 30 天内合并 PR
- 2
环境准备
这个项目没有提供开发容器、Dockerfile 或贡献指南，环境需要你自己搭建：先看它的 README，通用步骤见我们的新手贡献指南。
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
jump-dev/DiffOpt.jl 的其他 Issue
-
难度 3/5 1-2 天 新手友好度 55/100
jump-dev/DiffOpt.jl#362 · 1 条评论 ·
-
难度 5/5 一周以上 新手友好度 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 一周以上 新手友好度 35/100
jump-dev/DiffOpt.jl#331 · 1 条评论 ·
查看 jump-dev/DiffOpt.jl 的全部 Issue
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 74/100
OpenSourceAWE/SymbolicAWEModels.jl#431 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 76/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 72/100
EnzymeAD/Reactant.jl#3549 ·
维护者通常 1 天内回复
-
bug
难度 2/5 1-3 小时 新手友好度 75/100
-
bug help wanted
难度 2/5 1-3 小时 新手友好度 68/100
JuliaGeometry/Meshes.jl#1469 ·
维护者通常 1 天内回复