34 Matching Results

Search Results

Advanced search parameters have been applied.

Using ADIFOR and ADIC to provide Jacobians for the SNES component of PETSc

Description: The solution of large-scale nonlinear problems is important to many areas of computational science. The SNES component of PETSc provides a robust and flexible suite of numerical routines for the solving such problems. These routines generally utilize the Jacobian matrix. We present a strategy for using ADIFOR or ADIC to assist in the development of a subroutine for computing this matrix. We illustrate this strategy using one of the PETSc example programs and four different approaches to computing the Jacobian via automatic differentiation.
Date: November 1, 1997
Creator: Wu, Po-Ting; Bischof, C.H. & Hovland, P.D.
Partner: UNT Libraries Government Documents Department

Tetrahedral element shape optimization via the Jacobian determinant and condition number.

Description: We present a new shape measure for tetrahedral elements that is optimal in the sense that it gives the distance of a tetrahedron from the set of inverted elements. This measure is constructed from the condition number of the linear transformation between a unit equilateral tetrahedron and any tetrahedron with positive volume. We use this shape measure to formulate two optimization objective functions that are differentiated by their goal: the first seeks to improve the average quality of the tetrahedral mesh; the second aims to improve the worst-quality element in the mesh. Because the element condition number is not defined for tetrahedral with negative volume, these objective functions can be used only when the initial mesh is valid. Therefore, we formulate a third objective function using the determinant of the element Jacobian that is suitable for mesh untangling. We review the optimization techniques used with each objective function and present experimental results that demonstrate the effectiveness of the mesh improvement and untangling methods. We show that a combined optimization approach that uses both condition number objective functions obtains the best-quality meshes.
Date: July 30, 1999
Creator: Freitag, L. A. & Knupp, P. M.
Partner: UNT Libraries Government Documents Department

Integration of Mesh Optimization with 3D All-Hex Mesh Generation, LDRD Subcase 3504340000, Final Report

Description: In an attempt to automatically produce high-quality all-hex meshes, we investigated a mesh improvement strategy: given an initial poor-quality all-hex mesh, we iteratively changed the element connectivity, adding and deleting elements and nodes, and optimized the node positions. We found a set of hex reconnection primitives. We improved the optimization algorithms so they can untangle a negative-Jacobian mesh, even considering Jacobians on the boundary, and subsequently optimize the condition number of elements in an untangled mesh. However, even after applying both the primitives and optimization we were unable to produce high-quality meshes in certain regions. Our experiences suggest that many boundary configurations of quadrilaterals admit no hexahedral mesh with positive Jacobians, although we have no proof of this.
Date: November 1, 1999
Creator: KNUPP,PATRICK & MITCHELL,SCOTT A.
Partner: UNT Libraries Government Documents Department

Compiling fast partial derivatives of functions given by algorithms

Description: If the gradient of the function y = f(x/sub 1/,..., x/sub n/) is desired, where f is given by an algoritym Af(x, n, y), most numerical analysts will use numerical differencing. This is a sampling scheme that approximates derivatives by the slope of secants in closely spaced points. Symbolic methods that make full use of the program text of Af should be able to come up with a better way to evaluate the gradient of F. The system Jake described produces gradients significantly faster than numerical differencing. Jake can handle algorithms Af with arbitrary flow of control. Measurements performed on one particular machine suggest that Jake is faster than numerical differencing for n > 8. Somewhat weaker results were obtained for the problem of computing Jacobians of arbitrary shape.
Date: January 1, 1980
Creator: Speelpenning, B.
Partner: UNT Libraries Government Documents Department

Achieving Finite Element Mesh Quality via Optimization of the Jacobian Matrix Norm and Associated Quantities, Part II - A Framework for Volume Mesh Optimization and the Condition Number of the Jacobian Matrix

Description: Three-dimensional unstructured tetrahedral and hexahedral finite element mesh optimization is studied from a theoretical perspective and by computer experiments to determine what objective functions are most effective in attaining valid, high quality meshes. The approach uses matrices and matrix norms to extend the work in Part I to build suitable 3D objective functions. Because certain matrix norm identities which hold for 2 x 2 matrices do not hold for 3 x 3 matrices. significant differences arise between surface and volume mesh optimization objective functions. It is shown, for example, that the equivalence in two-dimensions of the Smoothness and Condition Number of the Jacobian matrix objective functions does not extend to three dimensions and further. that the equivalence of the Oddy and Condition Number of the Metric Tensor objective functions in two-dimensions also fails to extend to three-dimensions. Matrix norm identities are used to systematically construct dimensionally homogeneous groups of objective functions. The concept of an ideal minimizing matrix is introduced for both hexahedral and tetrahedral elements. Non-dimensional objective functions having barriers are emphasized as the most logical choice for mesh optimization. The performance of a number of objective functions in improving mesh quality was assessed on a suite of realistic test problems, focusing particularly on all-hexahedral ''whisker-weaved'' meshes. Performance is investigated on both structured and unstructured meshes and on both hexahedral and tetrahedral meshes. Although several objective functions are competitive, the condition number objective function is particularly attractive. The objective functions are closely related to mesh quality measures. To illustrate, it is shown that the condition number metric can be viewed as a new tetrahedral element quality measure.
Date: March 26, 1999
Creator: Knupp, P.M.
Partner: UNT Libraries Government Documents Department

ADIFOR working note {number_sign}2: Using ADIFOR to compute dense and sparse Jacobians

Description: ADIFOR is a source translator that, given a collection of Fortran subroutines for the computation of a ``function,`` produces Fortran code for the computation of the derivatives of this function. More specifically, ADIFOR produces code to compute the matrix-matrix product JS, where J is the Jacobian of the ``function`` with respect to the user-defined independent variables, and S is the composition of the derivative objects corresponding to the independent variables. This interface is flexible; by setting S = x, one can compute the matrix-vector product Jx, or by setting S = I, one can compute the whole Jacobian J. Other initializations of S allow one to exploit a known sparsity structure of J. This paper illustrates the proper initialization of ADIFOR-generated derivative codes and the exploitation of a known structure of J.
Date: January 1, 1992
Creator: Bischof, C. & Hovland, P.
Partner: UNT Libraries Government Documents Department

Tools for the automatic differentiation of computer programs

Description: Automatic differentiation (AD) is a methodology for developing sensitivity-enhanced versions of arbitrary computer programs. In this paper, we provide some background information on AD and basic implementation issues for the design of general purpose tools that can deal with codes from the Fortran and C family, address some frequently asked questions, and provide pointers for further study.
Date: December 31, 1995
Creator: Bischof, C. & Griewank, A.
Partner: UNT Libraries Government Documents Department

Making automatic differentiation truly automatic : coupling PETSc with ADIC.

Description: Despite its name, automatic differentiation (AD) is often far from an automatic process. often one must specify independent and dependent variables, indicate the derivative quantities to be computed, and perhaps even provide information about the structure of the Jacobians or Hessians being computed. However, when AD is used in conjunction with a toolkit with well-defined interfaces, many of these issues do not arise. They describe recent research into coupling the ADIC automatic differentiation tool with PETSc, a toolkit for the parallel numerical solution of PDEs. This research leverages the interfaces and objects of PETSc to make the AD process very nearly transparent.
Date: January 10, 2002
Creator: Hovland, P.; Norris, B. & Smith, B.
Partner: UNT Libraries Government Documents Department

Image based autodocking without calibration

Description: The calibration requirements for visual servoing can make it difficult to apply in many real-world situations. One approach to image-based visual servoing without calibration is to dynamically estimate the image Jacobian and use it as the basis for control. However, with the normal motion of a robot toward the goal, the estimation of the image Jacobian deteriorates over time. The authors propose the use of additional exploratory motion to considerably improve the estimation of the image Jacobian. They study the role of such exploratory motion in a visual servoing task. Simulations and experiments with a 6-DOF robot are used to verify the practical feasibility of the approach.
Date: March 1, 1997
Creator: Sutanto, H.; Sharma, R. & Varma, V.
Partner: UNT Libraries Government Documents Department

TENSOLVE: A software package for solving systems of nonlinear equations and nonlinear least squares problems using tensor methods

Description: This paper describes a modular software package for solving systems of nonlinear equations and nonlinear least squares problems, using a new class of methods called tensor methods. It is intended for small to medium-sized problems, say with up to 100 equations and unknowns, in cases where it is reasonable to calculate the Jacobian matrix or approximate it by finite differences at each iteration. The software allows the user to select between a tensor method and a standard method based upon a linear model. The tensor method models F({ital x}) by a quadratic model, where the second-order term is chosen so that the model is hardly more expensive to form, store, or solve than the standard linear model. Moreover, the software provides two different global strategies, a line search and a two- dimensional trust region approach. Test results indicate that, in general, tensor methods are significantly more efficient and robust than standard methods on small and medium-sized problems in iterations and function evaluations.
Date: December 1996
Creator: Bouaricha, A. & Schnabel, R. B.
Partner: UNT Libraries Government Documents Department

Tensor methods for large sparse systems of nonlinear equations

Description: This paper introduces censor methods for solving, large sparse systems of nonlinear equations. Tensor methods for nonlinear equations were developed in the context of solving small to medium- sized dense problems. They base each iteration on a quadratic model of the nonlinear equations. where the second-order term is selected so that the model requires no more derivative or function information per iteration than standard linear model-based methods, and hardly more storage or arithmetic operations per iteration. Computational experiments on small to medium-sized problems have shown censor methods to be considerably more efficient than standard Newton-based methods, with a particularly large advantage on singular problems. This paper considers the extension of this approach to solve large sparse problems. The key issue that must be considered is how to make efficient use of sparsity in forming and solving the censor model problem at each iteration. Accomplishing this turns out to require an entirely new way of solving the tensor model that successfully exploits the sparsity of the Jacobian, whether the Jacobian is nonsingular or singular. We develop such an approach and, based upon it, an efficient tensor method for solving large sparse systems of nonlinear equations. Test results indicate that this tensor method is significantly more efficient and robust than an efficient sparse Newton-based method. in terms of iterations, function evaluations. and execution time.
Date: December 1996
Creator: Bouaricha, A. & Schnabel, R. B.
Partner: UNT Libraries Government Documents Department

An implicit Smooth Particle Hydrodynamic code

Description: An implicit version of the Smooth Particle Hydrodynamic (SPH) code SPHINX has been written and is working. In conjunction with the SPHINX code the new implicit code models fluids and solids under a wide range of conditions. SPH codes are Lagrangian, meshless and use particles to model the fluids and solids. The implicit code makes use of the Krylov iterative techniques for solving large linear-systems and a Newton-Raphson method for non-linear corrections. It uses numerical derivatives to construct the Jacobian matrix. It uses sparse techniques to save on memory storage and to reduce the amount of computation. It is believed that this is the first implicit SPH code to use Newton-Krylov techniques, and is also the first implicit SPH code to model solids. A description of SPH and the techniques used in the implicit code are presented. Then, the results of a number of tests cases are discussed, which include a shock tube problem, a Rayleigh-Taylor problem, a breaking dam problem, and a single jet of gas problem. The results are shown to be in very good agreement with analytic solutions, experimental results, and the explicit SPHINX code. In the case of the single jet of gas case it has been demonstrated that the implicit code can do a problem in much shorter time than the explicit code. The problem was, however, very unphysical, but it does demonstrate the potential of the implicit code. It is a first step toward a useful implicit SPH code.
Date: April 1, 2000
Creator: Knapp, Charles E.
Partner: UNT Libraries Government Documents Department

Tetrahedral Element Shape Optimization via the Jacobian Determinant and Condition Number

Description: We present a new shape measure for tetrahedral elements that is optimal in the sense that it gives the distance of a tetrahedron from the set of inverted elements. This measure is constructed from the condition number of the linear transformation between a unit equilateral tetrahedron and any tetrahedron with positive volume. We use this shape measure to formulate two optimization objective functions that are differentiated by their goal: the first seeks to improve the average quality of the tetrahedral mesh; the second aims to improve the worst-quality element in the mesh. Because the element condition number is not defined for tetrahedral with negative volume, these objective functions can be used only when the initial mesh is valid. Therefore, we formulate a third objective function using the determinant of the element Jacobian that is suitable for mesh untangling. We review the optimization techniques used with each objective function and present experimental results that demonstrate the effectiveness of the mesh improvement and untangling methods. We show that a combined optimization approach that uses both condition number objective functions obtains the best-quality meshes.
Date: September 27, 1999
Creator: FREITAG,LORI A. & KNUPP,PATRICK
Partner: UNT Libraries Government Documents Department

New insights into input relegation control for inverse kinematics of a redundant manipulator. Part 1, On the orthogonality of matrices B and J and comparison to the extended Jacobian method

Description: A method for kinematically modeling a constrained rigid body mechanical system and a method for controlling such a system termed input relegation control (IRC) were applied to resolve the kinematic redundancy of a serial link manipulator moving in an open chain configuration in. A set of equations was introduced to define a new vector variable parameterizing the redundant degrees of freedom (DOF) as a linear function of the joint velocities. The new set was combined with the classical kinematic velocity model of manipulator and solved to yield a well specified solution for the joint velocities as a function of the Cartesian velocities of the end effector and of the redundant DOF variable. In the previous work a technique was proposed for selecting the matrix relating the redundant DOF variable to the joint velocities which resulted in it rows being orthogonal to the rows of the Jacobian matrix. The implications for such a selection were not discussed in. In Part 1 of this report a basis for the joint space is suggested which provides considerable insight into why picking the aforementioned matrix to be orthogonal to the Jacobian is advantageous. A second objective of Part 1 is to compare the IRC method to the Extended Jacobian method of Baillieul and Martin and other related methods.
Date: July 1, 1995
Creator: Unseren, M.A. & Reister, D.B.
Partner: UNT Libraries Government Documents Department

New insights into input relegation control for inverse kinematics of a redundant manipulator. Part 2, The optimization of a secondary criteria involving self motion of the joints

Description: The input relegation control (IRC) technique for redundancy resolution is extended to solve the problem of optimizing a scalar performance criteria representing a secondary objective to be accomplished via self motion of the joints. The criteria is defined to be the error between the vector of joint velocities and a new vector of ``corrective` joint velocities, which is minimized in a Eudidean norm sense. The corrective velocities represent a `corrective` action to be applied to the system and axe projected into the null space of the Jacoblan in the solution for the joint velocities. The report demonstrates that there exists a component in the solution for the joint velocities that induces self motion of the joints but is not a function of the ``corrective action``. A technique for eliminating this undesired component is presented. The method is compared to the well known gradient projection technique and its advantages are discussed.
Date: July 1, 1995
Creator: Unseren, M.A.
Partner: UNT Libraries Government Documents Department

Automatic differentiation, tangent linear models, and (pseudo) adjoints

Description: This paper provides a brief introduction to automatic differentiation and relates it to the tangent linear model and adjoint approaches commonly used in meteorology. After a brief review of the forward and reverse mode of automatic differentiation, the ADIFOR automatic differentiation tool is introduced, and initial results of a sensitivity-enhanced version of the MM5 PSU/NCAR mesoscale weather model are presented. We also present a novel approach to the computation of gradients that uses a reverse mode approach at the time loop level and a forward mode approach at every time step. The resulting ``pseudoadjoint`` shares the characteristic of an adjoint code that the ratio of gradient to function evaluation does not depend on the number of independent variables. In contrast to a true adjoint approach, however, the nonlinearity of the model plays no role in the complexity of the derivative code.
Date: December 31, 1993
Creator: Bischof, C.H.
Partner: UNT Libraries Government Documents Department

Using ADIFOR to compute dense and sparse Jacobians

Description: ADIFOR is a source translator that, given a collection of Fortran subroutines for the computation of a function,'' produces Fortran code for the computation of the derivatives of this function. More specifically, ADIFOR produces code to compute the matrix-matrix product JS, where J is the Jacobian of the function'' with respect to the user-defined independent variables, and S is the composition of the derivative objects corresponding to the independent variables. This interface is flexible; by setting S = x, one can compute the matrix-vector product Jx, or by setting S = I, one can compute the whole Jacobian J. Other initializations of S allow one to exploit a known sparsity structure of J. This paper illustrates the proper initialization of ADIFOR-generated derivative codes and the exploitation of a known structure of J.
Date: January 1, 1992
Creator: Bischof, C. & Hovland, P.
Partner: UNT Libraries Government Documents Department

On the calculation of Jacobian matrices by the Markowitz rule

Description: The evaluation of derivative vectors can be performed with optimal computational complexity by the forward or reverse mode of automatic differentiation. This approach may be applied to evaluate first and higher derivatives of any vector function that is defined as the composition of easily differentiated elementary functions, typically in the form of a computer program. The more general task of efficiently evaluating Jacobians or other derivative matrices leads to a combinational optimization problem, which is conjectured to be NP-hard. Here, we examine this vertex elimination problem and solve it approximately, using a greedy heuristic. Numerical experiments show the resulting Markowitz scheme for Jacobian evaluation to be more efficient than column by column or row by row evaluation using the forward or the reverse mode, respectively.
Date: January 1, 1991
Creator: Griewank, A. (Argonne National Lab., IL (United States)) & Reese, S. (Rensselaer Polytechnic Inst., Troy, NY (United States). Dept. of Mathematical Sciences)
Partner: UNT Libraries Government Documents Department

k-line iterative methods: a conjugate-gradient approach

Description: The generalized conjugate gradient scheme based on the k-line block Jacobi splitting A = M-N was studied for solving model two-dimensional parabolic and elliptic difference equations AU = F tilde. A represents the matrix ch/sup ..cap alpha../-h/sup 2/..delta../sub h/. Eigenvalues of M/sup -1/N cluster, and the cluster radii decrease as ch/sup ..cap alpha../ or k increases. Computations with k = 4, 8, 16, 32, and ch/sup ..cap alpha../ = 0, h, 2 are discussed.
Date: March 29, 1981
Creator: Kratzer, D.; Parter, S.V. & Steuerwalt, M.
Partner: UNT Libraries Government Documents Department

On the calculation of Jacobian matrices by the Markowitz rule

Description: The evaluation of derivative vectors can be performed with optimal computational complexity by the forward or reverse mode of automatic differentiation. This approach may be applied to evaluate first and higher derivatives of any vector function that is defined as the composition of easily differentiated elementary functions, typically in the form of a computer program. The more general task of efficiently evaluating Jacobians or other derivative matrices leads to a combinational optimization problem, which is conjectured to be NP-hard. Here, we examine this vertex elimination problem and solve it approximately, using a greedy heuristic. Numerical experiments show the resulting Markowitz scheme for Jacobian evaluation to be more efficient than column by column or row by row evaluation using the forward or the reverse mode, respectively.
Date: December 31, 1991
Creator: Griewank, A. & Reese, S.
Partner: UNT Libraries Government Documents Department

ADIFOR case study: VODE + ADIFOR

Description: ADIFOR can be used to generate the Jacobians required by VODE in a manner that is easy to use. We provide a template to interface the ADIFOR-generated code with VODE and show how the template is used in a sample system of stiff ordinary differential equation. The ADIFOR-generated code is about 10% faster than the hand-coded Jacobian for this example.
Date: August 1, 1992
Creator: Corliss, G.
Partner: UNT Libraries Government Documents Department

ADIFOR: Fortran source translation for efficient derivatives. ADIFOR Working Note No. 4

Description: The numerical methods employed in the solution of many scientific computing problems require the computation of derivatives of a function f: R{sup n} {yields} R{sup m}. Both the accuracy and the computational requirements of the derivative computation are usually of critical importance for the robustness and speed of the numerical method. ADIFOR (Automatic Differentiation In FORtran) is a source translation tool implemented using the data abstractions and program analysis capabilities of the ParaScope Parallel Programming Environment. ADIFOR accepts arbitrary Fortran-77 code defining the computation of a function and writes portable Fortran-77 code for the computation of its derivatives. In contrast to previous approaches, ADIFOR views automatic differentiation as a process of source translation that exploits computational context to reduce the cost of derivative computations. Experimental results show that ADIFOR can handle real-life codes, providing exact derivatives with a running time that is competitive with the standard divided-difference approximations of derivatives and which may perform orders of magnitude faster than divided-differences in cases. The computational scientist using ADIFOR is freed from worrying about the accurate and efficient computation of derivatives, even for complicated ``functions,`` and hence, is able to concentrate on the more important issues of algorithm design or system modeling. 35 refs.
Date: July 1, 1992
Creator: Bischof, C.; Corliss, G.; Griewank, A.; Hovland, P. & Carle, A.
Partner: UNT Libraries Government Documents Department

Magnetic charge and non-associative algebras

Description: We consider the possibility that the quantum mechanics of a nonrelativistic electron in the magnetic field of a magnetic charge distribution can be described in terms of a non-associative algebra of observables. It appears that the case of a point monopole is excluded, while that of a constant charge distribution is acceptable. 21 references.
Date: February 1, 1985
Creator: Guenaydin, M. & Zumino, B.
Partner: UNT Libraries Government Documents Department