Author: Matthieu Halard

Wikipedia says automatic differentiation is algorithmic!

In mathematics and computer algebra, automatic differentiation (auto-differentiation, autodiff, or AD), also called algorithmic differentiation, computational differentiation,^[1][2] is a set of techniques to evaluate the partial derivative of a function specified by a computer program.
https://en.wikipedia.org/wiki/Automatic_differentiation

No trace of symbolic differentiation, though being in the field of mathematics and computer algebra (also named symbolic computation in Wikipedia)! Furthermore I don’t know what an automatic differentiation is in mathematics: it could only be computer or robot algebra.

A computer algebra system usually deals with mathematical expressions, where the differentiation is said symbolic (though some variants exist in the naming, making conventional distinctions, refer to Wikipedia for symbolic computation vs computer algebra.).

If we speak of the differentiation of a program, then it should be said algorithmic. Why having chosen such an evocative word, if it can be replaced by the other ones?

However, a program can be seen as a particular procedure-type expression, taking as inputs the parameters and the body of the function; and conversely, an expression can be transformed into a procedure according to an evaluation mechanism (cf. Wikipedia, article Computer_algebra, section Expressions, paragraph 2). Then all is confused…

Nonetheless, to sum up:

algorithmic differentiation is a formal differentiation operating on the expressions that the elements of a program constitute.
symbolic differentiation is a formal differentiation operating on classical mathematical expressions.

The name auto-differentiation (or auto-diff) is a bad idea because auto itself means self and should not stand for automatic.

… and in no way symbolic nor numerical

Automatic differentiation is distinct from symbolic differentiation and numerical differentiation

Symbolic differentiation is an automatic differentiation: otherwise, I don’t know what we’re talking about, except for the high school student on his hand-made exercises.

Numerical differentiation is not automatic as a technique in itself but is probably the most easily automated method. And even it becomes, in a somewhat abusive manner, an algorithmic differentiation to the coarsest grain…

Both methods are defined only by their flaws

Symbolic differentiation faces the difficulty of converting a computer program into a single mathematical expression and can lead to inefficient code. Numerical differentiation (the method of finite differences) can introduce round-off errors in the discretization process and cancellation. Both of these classical methods have problems with calculating higher derivatives, where complexity and errors increase. Finally, both of these classical methods are slow at computing partial derivatives of a function with respect to many inputs, as is needed for gradient-based optimization algorithms.
Idem

How do these flaws prevent a method from being automatic? To lead to an inefficient code is to arrive at a code!

The ideas presented should be developed further.

… and automatic differentiation solves all these problems (sic)

It says it all in that title, which is the conclusion of the second paragraph. Neutral style.

My conclusion: a Wikipedia entry for algorithmic differentiation

It is necessary to return the term automatic to its usual meaning: automatic does not mean algorithmic, except abusively in a special context. Algorithmic differentiation is an automatic differentiation of code. The other automatic differentiations must be presented and shown how they differ, in particular their advantages and their disadvantages, and reference must be made to a special article for algorithmic differentiation, thus avoiding this double bias: usurped equivalence with one method and relegation of the competing methods.

Wikipedia is also faulty: a search for “algorithmic differentiation” or “computational differentiation” lands back to “Automatic_differentiation”. It’s marble-graved equivalent, you’re told!

Nonetheless, the relevant scheme involving symbolic and algorithmic differentiation must be used and detailed. See button below.

Numerical simulation and automatic differentiation

C++ associative operators are asocial

C++ has the drawback of being a bit binary… in its way of processing n-ary operations that does not care about the associative intent of the programmer. Do we have to wait for a quantum compiler with non-binary states to process together the operands associated by the parentheses? 😉

The problem

Although the + and * operators are mathematically associative, C++ treats their operands 2 by 2 from left to right. Thus a+b+c+d is seen as: ((a+b)+c)+d, without there being any way of specifying that one wants a sum of four operands other than by the less expressive call of a function such as sum(a, b, c, d). Admittedly, by the classic means of expression-templates, one could arrive at the desired result, but at the cost of losing respect for parentheses. For example, if the programmer writes (a+b+c)+d, a template-expression could group the first three terms together, but eventually aggregate the fourth. Unless a static operator () is added to the C++ standard, which would operate on the result of a+b+c, there is no way to keep track of parentheses.

This is a serious problem for a programming interface, because it is important to respect the user’s expressed intention.

Proposal for C++

Let Expr be a type on which we propose the possibility of defining the following + operator:

enum ExprOperator { ..., OpSum, ... OpProduct, ...};
struct Expr { ExprOperator; std::vector<Expr> operands;};
std::vector<Expr> to_vector(Expr... ee);

Expr operator+(Expr e, Expr... ee) // <- proposition
{
    return Expr { OpSum, to_vector(e,ee...) };
}

Note that such a program gets compiled but the operator+ is taken as a binary one. The variadic argument stands for one and only one We want it to be accepted as n-ary. With this, we are able to translate (a+b+c)+d into Expr{OpSum,{Expr{OpSum,{a,b,c}}, d} respecting the original.

Of course, all variants taking const Expr& and Expr&& are possible.

Implicit conversions or operations with other types

Often, because we have an Expr variable a, we want to add a numeric type, such as 1, as in a+1 or 1+a without specifying a+Expr(1) or Expr(1)+a, which would ruin the elegance of our expression. The + binary operator conventionally makes it possible to process this. How can it be generalized to a sum of multiple operands, such as in 1+a+b or a+1+b? We propose to use the concepts by allowing to write:

Expr operator+(Expr e, auto convertible_to<Expr>... ee)

The problem is that we don’t always have an Expr type in the first position, as in the case of 1+a+b. We therefore propose that C++ interpret this definition as: multiple operands, one of which is of type Expr and the others of type convertible_to<Expr>. Perhaps a more acceptable way for compilers would be to write:

Expr operator+(auto convertible_to<Expr>... ee1, Expr e, auto convertible_to<Expr>... ee2)

in which it would be the first among the operands which is of type Expr. This possibility would be reserved for non-Boolean associative operators (+,*,…). For Boolean operators, a better proposal should be given.

Presentation in SIA Congress in numerical simulation

Naupacte was present with a speaker at the SIA 2023 Congress in numerical simulation, during a Data & Optimization session. This was an opportunity to show what can be expected in terms of computational automation when one embarks on non-linear multiphysics modeling and simulation.

Automation of calculations

Automation of calculations leads to optimization of

the application developer,
the execution of calculations,
as well as the object studied, thanks to the optimal design algorithms.

The developer formulates its multiphysical coupling, while Navpactos takes care of the rest, i.e. the construction of the matrix and the second member obtained by assembly of finite elements. It is even sufficient to specify the construction of the second member, if one wants the tangent matrix, because it is deduced therefrom by derivation … with respect to the degrees of freedom. Navpactos takes care of everything.

Navpactos even takes care of more: examples of optimization in order 2, that is to say based on the Jacobian of the optimality equations, i.e. the Hessian of the Lagrangian, have been shown. With respect to the programming of the direct problem, it is sufficient to specify the parameters to be optimized and to formulate the cost function to be minimized. Everything else is automatic, which includes a differentiation of the tangent matrix! And also a linear search replaced by a search on a parabolic arc osculating the state curve.

Case Study and Convergence

The case shown was derived from non-linear elasticity with the two coefficients of the polynomial giving the imposed displacements on a face as parameters.

Example judiciously chosen (ah! chance) because it illustrates a consequence of poor conditioning: the direction of descent estimated by the hessian almost orthogonal to the gradient. The gain in iterations is colossal compared with a method of steepest descent.

The convergence of the residue of the gradient in the parameter space is very fast. This is a favorable case: an inverse problem where the cost function measures the difference on results with those of target parameters. This type of case validates the calculation of the derivatives a posteriori.

Naupacte at the “Trophées de la simulation et de l’IA”…

Three categories are available: start-up, innovation and co-design. The selection of the three “appointees” by category was made public, together with their descriptions.

Naupacte is appointed in the Innovation category.

Category Start-up

There are two projects for detecting defects or defect precursors, and one project a bit apart: a microprocessor to achieve European independence.

Category Innovation

There are two software programs, one of which is research-based, the other resulting from “industrial” integration, and THE general library for calculations: NAVPACTOS.

Published description of Navpactos

Navpactos is a C++ library that provides a language and toolbox for modeling and executing numerical simulation calculations. It unifies and simplifies the description of calculations, knows finite elements, meshes and sparse matrices, functions and fields; it builds and optimizes the corresponding computational chains “at run time” and knows how to derive them. To achieve this result, Naupacte has designed a tensor expression whose number of operators makes it possible to carry out the formal analyzes necessary for controls, optimization and derivation, in order to provide the indispensable ‘virtual computer’. Its richness makes the tensor, combined with the performance of its calculator, a communicable object at all the upper levels of the toolbox to ensure the unity of the programs and their simplicity by masking the calculations. Ergonomics and development power, reliability, performance and maintainability of the resulting code are the advantages given to the ambition of designers as to the optimization of personal skills and material resources. Its marketing phase begins, the product based on more than 3000 algebraic rules having been extensively tested by tens of thousands of unit tests for tensors, and hundreds of application cases.
NAUPACTE for NAVPACTOS (sur le site de l’Usine Nouvelle)

Links:

Forum Teratec 2022/Trophées

Cf page 19 of PDF: Catalogue du forum Teratec 2022.

Category co-design

Two projects involve AI but in very different ways, while another does not propose less than to pair Earth… digitally of course.

The audience Grand Prize

It shall be designated by public vote from among the 9 appointed.

What is automatic differentiation?

Mathematical models of physics abound with gradients, divergences, laplacians, curls, which are all spatial derivatives. Time derivatives occur in unstationnary models.

We are talking here of a more general derivation, aiming at as far as the derivation of the models themselves with respect to different kinds of variables.

Motivation

Such a derivation occurs as soon as the equations are established when they derive from a potential, or because their resolution uses the information given by the Jacobian when the model is linearized.

Beyond the resolution of the equation, the optimization of the parameters towards some criterion upon the solution will benefit from the knowledge of the derivatives of the latter with respect to these, also called sensitivity of the solution to the parameters.

Very different methods of differentiation

Whether they are unknown variables or data, once discretized, the problem consists in deriving a mathematical formula with respect to a list of its calculation inputs. Starting from a calculation code producing the result of the mathematical formula to be derived, there are three methods for obtaining a new code providing the derivative.

1. Finite difference

This is the simplest method: it consists in re-using the original code by slightly varying the input parameter considered and in making the difference between the two results, which is divided by the parameter deviation. With a second calculation for a value with the opposite deviation, a result is obtained with a second order accuracy instead of the first order.

Unfortunately, mathematics is contradicted by computer science, whose rounding will prevent differences from being accurate, because the decimals involved will be smaller and smaller, but always relative to the same central value. The precision is therefore necessarily limited. Moreover, the choice of the difference -epsilon- may sometimes never be satisfactory if the quantity to be derived is a sum the terms of which are of different order of magnitude without correlation to the order of magnitude of their variations… The small term of significant variation will be crushed!

Semi-analytical method

When the solution comes from the resolution of a linear system, rather than operating the difference on the true solutions, it is preferable to do it on the second members and to resolve the corresponding system. It’s faster and better. The matrix needs of course be constant or converged in the linearized case of a Newton algorithm. The analysis hence says the derivation can be transfered to the right-hand side. When the latter is calculated by finite difference, the method is called semi-analytical.

To do this, the code must no longer be a black box, as we need to get access to the resulting right-hand side, but that is only high-level insight. The so called semi-analytical sensitivity is proposed by some publishers.

2. Code differentiation (algorithmic, AD)

This is theoretically the easiest to use, thanks to automatic code differentiation tools: the code is provided, the output and input of which are specified, and the tool generates the code calculating the derivative. To do this, line after line, the tool writes the code containing value and derivative – for the basic functions have a known derivative – by direct chaining or inverse chaining (adjoint method). Initially limited to Fortran for its lack of pointers, the method was extended to C++ by other tools that took advantage of the overload of language operators to minimize the reengineering of the original code. The operations are overloaded to produce both value and derivative chaining instead of the sole value.

The algorithmic differentiation method has its best advantage in the case of complex inherited codes because, relying on the same calculations, it avoids debugging new code. It nevertheless requires expert human assistance to be operational and effective.

3. Symbolic derivation

Ideally, one would like to symbolically derive the formula and encode its calculation. Doing it by hand leads to a development time that was aimed to be avoided, while going through formal computational software (computer-algebra sofware, or C.A.S.) has some major drawbacks.

On the one hand, it is difficult to express the formula when it is based on complex concepts such as finite elements, integration schemes and meshes.
On the other hand, the developed result loses the tensor structure from which it is derived and does not give the best performance. The optimization of the code generation by these tools is based on the identification of the repetition of basic operations such as multiplications and sums of scalar variables, whereas there is theoretically better to do using tensors.

According to the authors of the Algorithmic Differentiation Wo rkshop organized by the GDR – Calculation Research Group of the CNRS on January 24, 2019 in Paris, this can lead to an explosion in the complexity of expressions.

Navpactos’ way of derivation

Upgrade your simulation code?

The opportunity to undertake the modernization of development processes can be brought about by

the desire to increase your productivity, reduce your maintenance, focus on your assets, capitalize on your developments
requirements for new formulations and sensitivity calculations
requirements for very fast assembly.

This is no doubt the opportunity to consider the use of NAVPACTOS, a language specially developed by Naupacte for these purposes. In fact, by removing the codes from their computational part, NAVPACTOS considerably lightens their development. What about performance? Far from being degraded, assembly speeds in particular are unprecedented.

The programming of an assembly by Finite Elements is an example where NAVPACTOS stands out for its simplicity and performance.

Simplifying rewriting is not the only advantage of this language, as it opens the way to generic programming with high reusability. Indeed, its power comes from being able to transfer formulations – or calculation definitions – thanks to its formal tensor calculation engine. Consider the features that handle such formulations: assembly, fields, meshes, algorithms like Newton’s, and therefore the higher-level modules that use them. All code based on NAVPACTOS benefits from the concept of formal calculation.

One possible opening allowed by rewriting with NAVPACTOS is the development of a parametric optimization algorithm using gradients automatically.

NAVPACTOS is therefore a tool to consider when the question arises of modernizing its calculation code.

With NAVPACTOS, you can easily compose the formulation and the corresponding system construction from the specifications of a numerical model, read for example from a command file, and then calculate and update them with a simple call. A dedicated language written in simple and expressive C++ allows you to follow the mathematical model.

Simply compile as usual your NAVPACTOS construction and resolution program. The outstanding performance of the calculations requested is delivered automatically thanks to a new method based on a few thousand internal rules.