Automatic Differentiation
With Higher Infinitesimals
or: Computational SmoothInfinitesimal Analysis in Weil Algebra

CASC 202
Hiromi ISHII (DeepFlow, Inc.
Slides available at: https://bit.ly/casc-smooth)

1

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Today’s Topic in short:

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

To Implement computational
Higher Infinitesimal Analysis,
utilising the connection between
Automatic Differentiation
andNilpotent Infinitesimal Analysis,
applying Gröbner basis technique
Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

So what?
Automatic Differentiation is a collection of methods to ef ciently
compute higher derivatives of the given function exploiting Chain Rule.
Nilpotent In nitesimal Analysis: an analysis using nilpotent in nitesimalsuch that d 2 = 0, d ≠ 0. (Analysis in the era of Newton or Gauß)
Although such an in nitesimal real contradicts classically, it can bejusti ed with topos theory and used to develop differential
geometry (cf: Synthetic Differential Geometry by Lawvere et al.).
Such in nitesimals can be algebraically formulated as Weil algebras.
Our Result:Combining Gröbner basis and Automatic Differentiation, we
propose an algorithm to achieve in nitesimal analysis with general,higher in nitesimals associated with Weil algebras.
We rst explore the exact connection b/w AD and Nilpotent Analysis.

fi

Repository: github.com/konn/smooth
fi

fi

fi

fi

fi

fi

fi

fi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review of Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smoothfifi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review of Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smoothfifi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

A Quick Review of Automatic
Differentiation(Forward-Mode)

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. IshiiThree ways of differentiation
Automatic Differentiation calculates
differential coef cients ef ciently andprecisely, using Chain Rule.

( f ∘ g)′(x) = ( f′ ∘ g)(x) ⋅ g′(x)Numerical Differentiation replaces
limits with small reals (e.g. Euler
method)Ef cient, but only an approximation.
Symbolic Differentiation expresses
functions as symbolic ASTs and thendifferentiate them symbolically.

{{y = f(x)h hf(x + h) − f(x − h)f′(x) ≈
2h

fi

￼

fi

￼

￼

Slides available at: bit.ly/casc-smoothfi￼Exact, but easy to explodeexponentially.
Repository: github.com/konn/smoothH. Ishii

Automatic Differentiation (Forward mode)
A coefficient ring ℝ

data AD a = AD { real

diff. coeff.

valuea, inifinitesimala }Linearity

AD f f' + AD g g' = AD (f + g) (f' + g')
AD f f' * AD g g' = AD (f * g) (f' * g + f * g')sin (AD f f') = AD (sin f) (f' * cos f)

Leibniz Rule

Chain Rule

Basic Idea: Storing the value and differential coef cient simultaneously.

x y = x + yd.
For F : ℝ → ℝ, its AD version F̂ :ℝ→
ℝ returnsdF( f(x)) + F( f(x))d, regarding inputs as of form f(x) + f′(x)d for somedxfunction f.
̂ + d).
The differential of F at x = a will be the coef cient of d in F(aWe use a shorthand:a + d corresp. to the differential at x = a of identity function f(x) = x.
:

fi

fi

:

:

:

Repository: github.com/konn/smooth

𝙳

𝙰

￼

𝙳

Slides available at: bit.ly/casc-smooth𝙰

𝙳𝙰

Automatic Differentiation with Higher Infinitesimals

Automatic Differentiation with Higher Infinitesimals

H. Ishii

DEMO

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Why does this work?

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

We can justify with thiswith the concepts of∞

C -ring and Weil algebra!

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review of Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smoothfifi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review f Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smooth
fi

o​

fi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

2. Justification of AD in termsof -rings and Weil algebras

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothH. Ishii

Justification
Forward Mode AD corresponds to the dual number ringℝ[d] = ℝ[X]/(X2), which has the canonical C∞-ring structure
2
The law d = 0 characterises the AD!

Def. (Lawvere)
A C∞-ring is a commutative ring where the product-preserving
map A( f ) : An → A is de ned for any C∞-function f : ℝn → ℝ.
"Smooth multivariate function naturally lifts to A"

More Rigorous Def

Example: the ring C∞(M) of real-valued smooth func. on a manifold M.
Speci cally, ℝ[d] is an instance of Weil algebras, which is the speciall
class of C∞-rings with a nilpotent in nitesimal structure!
fifiSlides available at: bit.ly/casc-smoothfi➡︎Automatic Differentiation with Higher Infinitesimals

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Power serieses form a∞
C -ringThm 2 (Lawvere)

The ring of multivariate formal power series ℝ[[ ]] has∞
the structure of C -ring via Taylor expansion.

Idea
∞
C
n

ℝ, g1, …, gn ∈ ℝ[[ ]], we let:Xα αℝ[[ ]]( f )( g ⃗) :=D ( f ∘ ⟨g1, …, gn⟩)(0).
∑n α!
α∈ℕ

𝕏

For f : ℝ

𝕏

𝕏

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Weil algebra
Def.

ℝ-vector space W is called a Weil algerba if there exists
an ideal I ⊆ ℝ[X1, …, Xn] such thatW ≅ ℝ[ ]/I, and (X1, …, Xn)k ⊆ I for some k.
Intuition: a real line augmented with nilpotent in nitesimals.
Each variable Xi corresponds to an in nitesimal.

Xi is nilpotent in the quotient ring ℝ[ ]/I.
Speci cally, it is nite dimensional as a vector-space;hence I is zero-dimensional ideal!

fi

fi

𝕏

fi

fi

Repository: github.com/konn/smooth𝕏

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii∞

Weil ring is a C -ringThm (Lawvere)
Any Weil algebra W = ℝ[ ]/I has the canonical C∞-structure.
This follows from the following lemma:

Lem 1
For any ring-theoretic ideal I on a C∞ -ring A , A/I has the canonicalC∞-structure induced by the quotient map:

(A/I)( f )([x1]I, …, [xm]I ) := [A( f )(x1, …, xm)]

I

Since I is zero-dimensional, ℝ[[X]]/I ≅ ℝ[X]/I is a C∞-ring.
In particular, dual number ring ℝ[d] ≅ ℝ[X]/(X 2) is also a
C∞-ring!
𝕏

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii∞

The C -structure of ℝ[d]We let f(a + bd) = f(a) + bf′(a)d for theunivariate case.
What about multivariate case f : ℝ

∞
C
n

ℝ?

∞

￼

This can be calculated from the C-structure of the univariate formal power
series ring by cutting-off the terms at thedegree 1 and replacing X with d.

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii∞

The C -structure of ℝ[d]Letting gi = ai + bi X (i = 1,…, n),ℝ[[X]]( f )(g) ⃗d⃗= f( g (0))+ ( f ∘ ⟨g1, …, gn⟩)(0)X + …
dx= f(a1, …, an) + (g′1(0) + …g′n(0)) ⋅ f′(g1(0), …, gn(0)) X + …
= f(a1, …, an) + (b1 + … + bn) ⋅ f′(a1, …, an) X + …

Hence, by quotienting by I = (X 2), we have
￼

￼

￼

￼

ℝ[d]( f )(a1 + b1d, …, an + bnd) = f( a ⃗) + (b1 + … + bn)f′( a ⃗) ⋅ d .
This coincides with the de nition of AD when n = 1!

fi

Repository: github.com/konn/smooth￼

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Summary(Forward Mode) Automatic Differentiation is amethod to compute differentials of composite
functions of smooth maps ef ciently and precisely
by storing the direct value and differential
coef cient at some point simultaneously.
This can be viewed as utilising the structure of C
-ring of the dual number ring ℝ[d] = ℝ[X]/(X2).

∞

The dual number ring is an instance of Weil algebra
which axiomatises the real line with nilpotent
in nitesimal.

fi

fi

fi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review f Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smooth
fi

o​

fi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Outline1.

A Quick Review f Automatic Differentiation(Forward-Mode)∞2.

Justi cation of AD in terms of C -rings andWeil algebras

3.

Computational Higher-Order In nitesimal
Analysis with Weil Algebras

Repository: github.com/konn/smooth
fi

o​

fi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

3. Computational HigherOrder Infinitesimal Analysis
with Weil Algebras

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

3. Computational HigherOrder Infinitesimal Analysis
with Weil Algebras

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Why Weil algebras?
Q.

Why we have referred to Weil algebra and∞C -rings, instead of just saying "Forwardmode AD can be justi ed by Taylor expansionof smooth maps"?

A.

To generalise Forward Mode AD tomultivariate / higher-order differentials andhigher-order nilpotent in nitesimals.

fifi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Higher-order diff. with Weil algebras
A tensor of the dual number rings can be used to compute higher
derivatives. Let:ℝ[d1, …, dn] = ℝ[X1, …, Xn]/(X i2 ∣ i ≤ n) ≅ ℝ[d] ⊗ℝ … ⊗ℝ ℝ[d]n-copies

Then, by an easy induction, we have:ℝ[ d ](⃗ f )(x + d1 + … + dn) =

∑

0≤i≤n

f (i)(x)σni ( d ),⃗where σki is the k-variate elementary symmetric expr. of degree i.

In particular, we can get k-th derivative of f by looking at the⃗ f )(x + d + … + d )!
coef cient of d1…dk of ℝ[ d ](1n

It has all the information of derivatives up to nth
Likewise, higher derivatives of multivariate functions can becomputed by a nite tensor products of the dual number rings.

fi

fi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

DEMO

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Our Contribution

Further Generalisation
The structure of a Weil algebra W = ℝ[ ]/I is determinedby an ideal I with (X1, …, Xn) ⊆I.

W is a nite-dimensional vector space; i.e, I is zerodimensional.

We can employ Gröbner basis algorithms to compute
their ℝ-algebra structure.
For C∞-structures of in nitesimal, we can rst calculate in
the formal power series ring, cutoff at the appropriate
degree and take the quotient map.
In this way, we can do the calculation in the space withgeneral nilpotent in nitesimals on computers!
Repository: github.com/konn/smooth
fi

fi

fi

fi

𝕏

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Weil algebra Test
Algorithm 1 (WeilTest)
Input: a polynomial ideal I ⊆ ℝ[X]Is I ⊆ ℝ[ ] a zerodimensional ideal? No → Not a Weil algebra
Computer the Gröbner basis of?

X1, …, Xn ∈I

I with Gröbner algorithms

No → Not a Weil algebra
Yes → Returns monomial basis, an upper bound of multidegree, andthe multiplication table ([6])

With these information, algebraic operations on Weil algebra W is easy.
In our paper, we also returns the expression of nontrivial monomials as
the linear combination of basis for the sake of ef ciency.
Repository: github.com/konn/smoothfi𝕏

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii∞

C -structure of Weil algebra
Lem 1: the C∞-structu.re of a Weil algebra is given by the quotientingthat of ℝ[[X]].
By Thm. 2, the C∞-structure of ℝ[[X]] is given by:
Xα αℝ[[X]]( f )(g1, …, gm) =D (f ∘ ⟨g1, …, gm⟩)(0) .
∑n α!
α∈ℕ

We need an arbitrary partial derivatives of composite functions.
In general, AD calculating higher-order derivatives of multivariate
functions is called Tower-mode AD.
Tower-mode AD and ℝ[[X]] coincides modulo the factor of
α! = α1 ! ⋅ ⋯ ⋅ αm !.

Here, we think about C∞-maps, derivatives are commutative.

We proposed, in [9], a variant of Tower AD optimised for this case(Appendix)
Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals∞

H. Ishii

Computing C -structureof Weil algebra
Algorithm 2 (LiftWeil)∞n C

Input: f : ℝℝ a smooth map admitting Tower AD,

Information of Weil algebra W = ℝ[X1, …, Xn]/I given by Alg. 1 (Especially,monomial basis {X β1, …, X βk} and multidegree upper bound α of W), andan element w ⃗ = (w1, …, wn) ∈ W n.

Output: W( f )( w ⃗ ) ∈ W : given by C∞-structure of W.

1. Take the representative polynomials g ⃗ of w .⃗2. Calculate h ∈ ℝ[X] given by cutting off ℝ[[X]]( f )( g ⃗ ) at the upper boundα (Using Tower AD and multiply by factorial).

3. Calculates h̄G =∑i≤kck X βk and return (c1, …, ck).

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

Application 1: More

H. Ishii

efficient higher derivatives"Tensor of dual numbers" approach needs n-many variables tocalculate nth derivative.
The result much duplicate and redundant informations.
In particular, # of terms explodes to 2n to calculate up to nth!
We can save space and time using the following lemma:

Lem
For ε = (X) ∈ ℝ[X]/X n and smooth f : ℝ → ℝ, we have:

1 (i)ℝ[ε]( f )(x + ε) =f (x)εi∑ i!
0≤i<nSlides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Higher derivatives: benchℝ[d] ⊗ … ⊗ ℝ[d]

10
1
0.1
0.01

1000
100
10
1
0.1
0.01
1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

Alloc (MB)Alloc (MB)

0.001

1000
10
0.1

1000
100
10
1
0.1
0.01

0.001
1 2 3 4 5 6 7 8 9 10

f(x) = xe

1 2 3 4 5 6 7 8 9 10

−x2+x

10000
100
1
0.01
1 2 3 4 5 6 7 8 9 10

Alloc (MB)Time (μsec)

100

ⁿ⁺¹

x
Time (msec)

Time (msec)

1000

f(x) = ef(x) = xℝ[ ] /

100
1
0.01
1 2 3 4 5 6 7 8 9 10Environment: virtual Linux environment on GitHub Actions (Standard_DS2_v2 Azure instance)with two Intel Xeon Platinum 8171M virtual CPUs (2.60GHz) and 7 GiB of RAM.

𝑋

𝑋

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Application 2: Tensors
The tensor W1 ⊗ℝ W2 of Weil algebras W1, W2 is again a Weil
(Lem 4):ℝ[[X]]/I ⊗ℝ ℝ[[Y]]/J ≅ ℝ[[X, Y]]/⟨I, J⟩
The structure of tensors can be calculated with convolution (Alg. 4).
Using tensors we can combine arbitrary, multiple Weil algebras.
In particular, we can "package" higher-order ADs as Weilalgebras, and "compose" them with tensors!

Ex.
Letting ℝ[ε] = ℝ[x]/(x n+1), ℝ[δ] = ℝ[y]/(ym+1),

1 i j(ℝ[ε] ⊗ℝ ℝ[δ])( f )(x + ε, y + δ) =∂x ∂y f(x, y).
∑ i!j!
0≤i≤n
0≤ j≤mSlides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

DEMO

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Summary
Forward Mode Automatic Differentiation corresponds to thenilpotent in nitesimal analysis of second-order.
Justi ed by the theory of C∞-rings by Lawvere et al.
In particular, Forward AD is an instance of Weil algebra
which has nilpotent in nitesimals.
These concepts came from Synthetic Differential Geometry.
Our Result: Combining AD and algorithms for zero-dimensional
ideals, we achieved computational in nitesimal analysis withhigher-order nilpotent in nitesimals on computers.
Future Works: Optimisation, Synthetic treatment of Differential
Geometry on Computers

fi

fi

fi

fi

fi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Existing Works
Nishimura and Osoekawa (2007) applies zero-dimensionalalgorithms to calculate the fundamental relation of generatorsof limit of Weil algebras.
They focus on the utility application to develop the theoryof Weil algebra in SDG and not interested in computing
differentials of smooth functions.
Our interest is other direction - our central concern iscomputational in nitesimal analysis and smooth-ringcomputation.
Our contribution clari es the connection of ADs and SIAs,
which has been already pointed out but not discussed
thoroughly, and implement it on the computer.

fifi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Future Works
Develop Synthetic Differential Geometry (by Lawvere
et al.) on computers using higher in nitesimals.
In SDG, general Weil algebras such asℝ[d1, …, dn] = ℝ[x1, …, xn]/(didj ∣ i, j ≤ n) are used todevelop theory.

This opens a door to synthetic treatment of differentialgeometric objects on computer.
Challenge: although C∞(M) is nitely-presented as a C∞
-ring but, not so as an ℝ-algebra!

Investigate the connection with othersuch as Reverse-Mode.

fl

Repository: github.com/konn/smoothfifi

Slides available at: bit.ly/casc-smoothavours of ADs,

Automatic Differentiation with Higher Infinitesimals

H. Ishii

References
1. Moerdijk, I. and Reyes, G. E. Models for Synthetic Differential Geometry. Springer-Veriag New
York, lnc.,1991.
2. Kmett, E., The ad package. https://hackage.haskell.org/package/ad
3. 稲葉一浩「自動微分 ≪フォワード・モード≫」http://www.kmonos.net/
wlog/123.html#_2257111201
4. Elliott. C, Beautiful Differentiation. ICFP 2009.
5. Cox, D., Little, J. and O'Shea, D., Ideals, Varieties, and Algorithms. 3rd ed. Springer
Science+Business Media, 2007.
6. Cox, D., Little, J. and O'Shea, D., Using Algebraic Geometry. Springer Science+BusinessMedia, 2005.
7. Nishimura, H. and Osoekawa, T., General Jacobi Identity Revisited Again. 2007.
8. I., Automatic Differentiation With Higher In nitesimals, or Computational Smooth In nitesimal Analysis
in Weil Algebra. To appear in CASC 2021.
9. I., A Succinct Multivariate Lazy Multivariate Tower AD for Weil Algebra Computation. In: Fujimura,M. (ed.) Computer Algebra. RIMS Kôkyûroku, pp. 104–112. Research Institute forMathematical Sciences, Kyoto University, Kyoto, Japan (2021). arXiv:2103.11615

Repository: github.com/konn/smoothfifi

Slides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. IshiiThank you!

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Any Questions?
Forward Mode Automatic Differentiation corresponds to thenilpotent in nitesimal analysis of second-order.
Justi ed by the theory of C∞-rings by Lawvere et al.
In particular, Forward AD is an instance of Weil algebra
which has nilpotent in nitesimals.
These concepts came from Synthetic Differential Geometry.
Our Result: Combining AD and algorithms for zero-dimensional
ideals, we achieved computational in nitesimal analysis withhigher-order nilpotent in nitesimals on computers.
Future Works: Optimisation, Synthetic treatment of Differential
Geometry on Computers

fi

fi

fi

fi

fi

Slides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

AppendicesSlides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

Categorically Rigorous

H. Ishii

Definition of smooth rings
Def. (Lawvere)
Let CartSp be the category of all nite-dimensional Euclidean
spaces and C∞-maps between them.
A C∞-ring is a product-preserving functor A : CartSp → Sets.

Repository: github.com/konn/smoothfiSlides available at: bit.ly/casc-smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Succinct Tower ADf (a)fy (a)

fx (a)

fz (a)

fx2 (a) fxy (a)fxz (a) fy2 (a) fyz (a)
XX
X

XX
X

XX XX
X X

XX
X

XX
X

XX
X

XX
X

XX
X

fz2 (ba)XX
X

Stores differentials as an in nite tree with decaying branching.
Goes right if no further differentiation will be taken for preceding variables.

fiSlides available at: bit.ly/casc-smooth

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Tower bench: Univariate
Sparsediffs

Our Method

12f(x) = e
Time (μsec)

Time (μsec)

f(x) = x
9
6
3
0

40
30
20
10
0

0 1 2 3 4 5 6 7 8 9 10

0 1 2 3 4 5 6 7 8 9 1050140
Alloc (KB)

Alloc (KB)

x

38
25
13
0
0 1 2 3 4 5 6 7 8 9 10

Slides available at: bit.ly/casc-smooth

105
70
35
0
0 1 2 3 4 5 6 7 8 9 10

Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

H. Ishii

Tower bench: Multivariate
Sparsey2

160f(x, y, z) = sin x ⋅ eTime (μsec)

Time (μsec)

f(x, y) = sin x ⋅ e

Our Method

120
80
40
0

500

375
250
125
0
1

Alloc (KB)

Alloc (KB)

1 2 3 4 5 6 7 8 9 10
500
375
250
125

y2+z

3

5

7

9

11

900
675
450
225
0

0
1 2 3 4 5 6 7 8 9 10
Slides available at: bit.ly/casc-smooth

1 2 3 4 5 6 7 8 9 10
Repository: github.com/konn/smoothAutomatic Differentiation with Higher Infinitesimals

3

2

3

H. Ishii

Tower bench: ℝ[x, y]/(x − y , y )Sparsef(x) = xf(x) = ef(x, y, z) = sin x ⋅ e

250
125
1

x + d

525
350
175
0

dense

1050
700
350
0

1

x + d

dense

1600

4

1050

1200

3

350
0

1

x + d

dense

Alloc (MB)

1400

700

800
400
0

Slides available at: bit.ly/casc-smooth

x 2+x

1400
Time (μsec)

375

Alloc (KB)

Alloc (KB)x

700
Time (μsec)

Time (μsec)

5000

Our Method

x + d

dense

x + d

dense

1

x + d

dense

2
1
0

1

1

Repository: github.com/konn/smooth