Sparse Jacobians #227
Replies: 4 comments 5 replies
-
I'm not sure ATM how a general solution yet efficient can be designed for this (but I believe it is possible). This would highly depend on the sparsity structure of the problem. For example, for block diagonal matrices (which your example fits in this case), with say, 4x4 block size, you could group the functions in sets of 4 and then compute the Jacobian of these 4 functions. But for more complicated and unstructured sparsity, the strategy would not be as trivial (but still possible, although you may have to know in advance the "dependence network" among functions and variables). Another solution to your example would be: Define Can you see that you are not evaluating |
Beta Was this translation helpful? Give feedback.
-
One way to do it would be to add the functions together, since they are linearly independent by definition. So for example, one could modify the function as:
Then take the gradient w.r.t. x=[2, 1] and then insert the values back into the Jacobian based on its pattern. I will see if I can develop a solution based on this. |
Beta Was this translation helpful? Give feedback.
-
I can only get this to work if taking the approach in the first post, i.e. changing all the independent functions such that they depend on x[0] only and then taking the derivative w.r.t. x[0]. For a 10000 x 10000 Matrix I can compute the Jacobian in 4 ms, whereas the computation takes 34,8 seconds for the typical naive approach going through all the derivative w.r.t to all x. The only problem is that then it only works if all the values are the same, i.e. x[0]=x[1]=x[2]. I can get it to work if splitting up the functions also as suggested by @allanleal, but I don't see a good approach for making this into a generalised method that works for arbitrary size functions. Not sure how to continue at this moment. |
Beta Was this translation helpful? Give feedback.
-
I found an article about this: What Color Is Your Jacobian? Graph Coloring for Computing Derivatives. It would be great if this can be implemented. |
Beta Was this translation helpful? Give feedback.
-
Hi,
I have been using autodiff for a while now and I really like the software a lot. Great job.
I want to try and improve performance for sparse Jacobians. Consider the function, f: R^2 -> R^2 where
f_1 = x_1
f_2 = cos(x_2)
The Jacobian can be computed by autodiff as in example-forward-jacobian-derivatives-using-eigen. The function is defined as:
VectorXreal f(const VectorXreal& x){ VectorXreal out(2); out << x[0], cos(x[1]); return out; }
Then, the autodiff Jacobian function is called to give the solution:
MatrixXd J = jacobian(f, wrt(x), at(x), F);
However, note that the Jacobian is diagonal and it could be computed using one cycle in the ForEachWrtVar loop instead of two cycles since the two functions are independent. This of course becomes much more relevant for a larger matrices.
The idea is to identify what rows in the Jacobian can be computed together, for example, in this case, f_1 and f_2 both belongs to group 1. Hence, the function could be modified as:
f_1 = x_1
f_2 = cos(x_1)
To differentiate both functions using only one cycle instead of two. However, now the second function is evaluated at x1 instead of x2! So, I need some functionality to evaluate the gradient at different row-values.
Any ideas for how I could improve this would be very welcome :-)
Best regards
Kristian
Beta Was this translation helpful? Give feedback.
All reactions