Rewrite Jacobian by source code transformation for SX

[casadibot]

The current generation of Jacobian expression for SX-graphs is inefficient and is starting to become a bottle neck in algorithm. For example, there is a bug preventing the forward mode AD (see #23) to be used, making it necessary to rely on adjoint mode AD all the time. The function needs to be rewritten with the following improvements:

• The new implementation should make use of the already calculated sparsity pattern (see ticket Detecting sparsity patterns of Jacobians #126), as this is a prerequisite for all of the advanced methods for calculating complete Jacobians, described for example in Gebremedhin/Manne/Pothen "What Color Is Your Jacobian? Graph Coloring for Computing Derivatives". The new implementation should use full, unidirectional coloring using a direct method (distance-2 coloring), described in the article. Both forward and adjoint mode should be supported.
• The new Jacobian function supports calculating several blocks of the Jacobian simultaneously. This should be exploited. In a future version, a partial algorithm (see article) could be used to calculate only the parts of the Jacobian that we are interested in.
• The algorithm can later be extended to include bidirectional algorithms and algorithms that exploit sparsity.

Created by jaeandersson at: 2011-06-04T12:14:14
Last updated at: 2012-01-23T12:45:19

---

Comment 1 by jaeandersson at 2011-06-04T22:12:35

With the sparsity detection implemented (ticket #126) there is nothing blocking the ticket anymore.

---

Comment 2 by jaeandersson at 2011-06-05T00:10:42

There is a software "ColPack", which appears to implement all of the latest algorithms for this. The license is LGPL. It might be a smart idea just to interface it instead of rewriting everything.

---

Comment 3 by jaeandersson at 2011-06-06T11:43:51

Created a ticket for interfacing ColPack: #129

---

Comment 4 by jaeandersson at 2011-06-06T11:48:48

A new version of the Jacobian calculation has been implemented. The new version supports forward and adjoint modes (both working well for the test problems) and allows plugging in arbitrary unidirectional or bidirectional seed matrices. It also supports multiple input and multiple output blocks.

Still missing is a basic working coloring algorithm. A greedy distance 2 algorithm has been written, but does not yet work properly for all the test problems.

---

Comment 5 by jaeandersson at 2011-06-14T18:16:45

In revision 68dfebb: Added a greedy graph coloring algorithm that can be used to provide unidirectional colorings for forward or adjoint mode AD.

The coloring doesn't work when multiple Jacobians are requested simultaneously.

---

Comment 6 by jaeandersson at 2011-08-16T16:55:51

Milestone Version 1.4.0beta deleted

---

Comment 7 by jaeandersson at 2012-01-17T19:14:18

Won't make it for Version 1.4.0beta.

---

Comment 8 by jaeandersson at 2012-01-20T23:17:33

Closing the ticket.

There are two remaining tasks in this ticket:

• Multiple Jacobian blocks -> treated by Multiple jacobian blocks in XFunctionInternal::jacGen #337.
• Advanced graph coloring techniques -> treated by ticket Bidirectional coloring, star coloring, partial coloring #205.