Possible performance improvement?
Personne n'a encore pris cette issue.
Évaluation
- Difficulté
- 5/5
- Temps estimé
- Plus d'une semaine
- Accessibilité débutants
- 35/100
- Type d'issue
- Fonctionnalité
- Clarté
- Plutôt claire
- Activité
- À l'abandon
- Stack technique
- julia
- Domaine
- performance
Piste de recherche
Commencez dans src/NonLinearProgram/NonLinearProgram.jl autour de ForwCache et du calcul de Δs, puis suivez _compute_sensitivity et _compute_derivatives_no_relax dans src/NonLinearProgram/nlp_utilities.jl. Comparez la résolution K\N existante avec des résolutions lazy de RHS vectoriels pour la différentiation directe et inverse. C’est terminé lorsque les résultats des produits Jacobienne-vecteur sont préservés tout en réduisant le travail et la mémoire inutiles liés aux systèmes linéaires.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
Description
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
- Langage dominant
- Julia
- Étoiles
- 146
- Forks
- 21
- Métriques de merge des PR
- Aucune PR mergée en 30 j
Préparer son environnement
Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Autres issues de jump-dev/DiffOpt.jl
-
Difficulté 3/5 1-2 jours Accessibilité débutants 55/100
jump-dev/DiffOpt.jl#362 · 1 commentaire ·
-
Difficulté 5/5 Plus d'une semaine Accessibilité débutants 25/100
jump-dev/DiffOpt.jl#358 · 2 commentaires ·
-
Difficulté 3/5 1-2 jours Accessibilité débutants 55/100
jump-dev/DiffOpt.jl#348 ·
-
good first issue
Difficulté 4/5 3-5 jours Accessibilité débutants 48/100
jump-dev/DiffOpt.jl#336 · 4 commentaires ·
-
Difficulté 5/5 Plus d'une semaine Accessibilité débutants 35/100
jump-dev/DiffOpt.jl#331 · 1 commentaire ·
Toutes les issues de jump-dev/DiffOpt.jl
Issues similaires
-
Difficulté 1/5 Moins d'une heure Accessibilité débutants 62/100
SciML/DataDrivenDiffEq.jl#694 ·
-
Difficulté 2/5 1-3 heures Accessibilité débutants 76/100
JuliaLang/LinearAlgebra.jl#1834 ·
Les mainteneurs répondent en général sous 1 jour
-
`RawAcquisitionData(acqData)` writes the repetition into the `average` counterPeut-être pris Une pull request liée à cette issue est ouverte ou déjà fusionnée. Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 82/100
MagneticResonanceImaging/MRIReco.jl#332 ·
Les mainteneurs répondent en général sous 1 jour
-
Docstrings show df:DataFrame and an undefined function is exportedPeut-être pris Une pull request liée à cette issue est ouverte ou déjà fusionnée. Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 85/100
-
Difficulté 2/5 1-3 heures Accessibilité débutants 65/100
Les mainteneurs répondent en général sous 1 jour