Jacobian sparsity

The solution of the system (2.219) should be achieved by the method that best exploits Jacobian sparsity and structure. 

Schubert s updating formula is particularly useful in the case of large-scale ( ) sparse systems, since it preserves Jacobian sparsity and executes only the calculations for nonzero derivatives. 

It is not hard to change the variables to make the Jacobian sparse, and it is simple to run a simulation using DAEPACK rather than DASPK or VODE, to see whether the sparsity-aware software is less demanding of computer... 

As originally proposed, the sparsity of the jacobian matrix is destroyed by Broyden s method. Two procedures (or modifications) which preserves the sparsity of the jacobian matrices are presented. The procedures are demonstrated by use of simple algebraic examples and applied to the solution of distillation problems whose jacobian matrices are sparse. 

Two methods have been proposed for retaining the desirable characteristics of Broyden s method and eliminating the undesirable characteristic of the loss of sparsity of the jacobian matrix through the use of inverses. In both of these modifications of Broyden s method, the necessity for the development of analytical expressions for the partial derivations is eliminated. To initiate the calcula-tional procedure in each of these modified versions of Broyden s method, the partial derivatives appearing in the jacobian matrix are evaluated numerically, and the jacobian matrix is updated in subsequent trials through the use of functional evaluations. The first modified form of Broyden s method is the one proposed by Gallun and Holland,9 and the second modification is the one proposed by Schubert.21... 

Thus, if J0 is sparse and a sparse factorization is available, Broyden s procedure can be implemented while effectively maintaining the sparsity of the jacobian. The algorithm for effecting these calculations in an efficient manner is developed as follows. Suppose that it is desired to solve... 

When the number of equations and variables is quite large, each equation often depends on a reduced set of variables. It is necessary to exploit the sparsity of the Jacobian matrix so as to reduce memory allocation while saving CPU time. In particular, the following expedients are essential ... 

Using a DAE solver that accepts the Jacobian existence matrix, that is, an incidence matrix only. This provides the solver with the possibility to completely exploit the system s sparsity, but not its overall structure. Nevertheless, it is often not possible to provide the Jacobian incidence matrix, especially when the system is very large or when the incidence matrix changes as part of an iterative process. 

It is possible to exploit some formulae to update the Jacobian, which are able to preserve its sparsity. However, if some elements are constant, they should not... 

It is possible to update the Hessian as if it were the Jacobian of gradient of the objective function. When the Jacobian of a system of equations is updated, it is possible to preserve its sparsity by means of the Schubert s formula (7.103). 

Jacobians numerically as full matrices. However, when a sparsity pattern is provided, the solver uses it... 

As mentioned above the usual choice for the solution algorithm of the coupled system (4.1) is the Newton method. In our case it cannot be used due to the non-sparsity of the Jacobian matrix but it may lead to the development of an appropriate variant. Using Newton s method at a current position (x, y ), the system of equations... 

We could reduce the effort required to solve the problem by providing the Jacobian as a second output argument of our function routine. In polymer.f low 1 D.m, fsolve is provided with a sparse matrix that is nonzero only at those elements that are nonzero in the Jacobian, through the JacobPattern option in optimset. This sparsity information helps fsolve to... 

In the former option, the nser supplies a sparse matrix S whose sparsity pattern (location of nonzero elements) matches that of the Jacobian. That is, even though the Jacobian may be difficult to compute analytically, the user can at least specify that only a small subset of Jacobian elements are known to be nonzero, fsolve can use this information to reduce the computational burden and memory requirement when generating an approximate Jacobian. With JacobMult , the user supplies the name of a routine that returns the product of the Jacobian matrix with an input vector. The usefulness of this option will become clearer after our discussion of iterative methods for solving linear algebraic systems in Chapter 6. 

Implicit methods such as odelBs require the Jacobian matrix J = df /dx". If only a routine such as calc.f is supplied, odelBs estimates the Jacobian by finite differences. For large, sparse systems, the work associated with Jacobian estimation can be reduced significantly by supplying a matrix with the same sparsity pattern as the Jacobian, through the "JPattern" field of Options. Even better, we can supply a routine that computes the Jacobian,... 

Figure 6.11 Effect of stacking on the sparsity pattern of the Jacobian for a BVP involving the 1-D transport of four fields, with local coupling of each field through the source terms. A grid of 50 points is used to discretize the PDEs. Plot generated by BVP.fieIdJPattern.m.

---