# Unraveling Femtosecond Spin and Charge Dynamics with EUV T-MOKE Spectroscopy

Henrike Probst  Christina Möller  Maren Schumacher  I. Physikalisches
Institut, Georg-August-Universität Göttingen, Friedrich-Hund-Platz 1, 37077
Göttingen, Germany  Thomas Brede  Institute of Materials Physics, University
of Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany  John Kay
Dewhurst  Max-Born-Institute for Non-linear Optics and Short Pulse
Spectroscopy, Max-Born Strasse 2A, 12489 Berlin, Germany  Marcel Reutzel
Daniel Steil  I. Physikalisches Institut, Georg-August-Universität Göttingen,
Friedrich-Hund-Platz 1, 37077 Göttingen, Germany  Sangeeta Sharma  Max-Born-
Institute for Non-linear Optics and Short Pulse Spectroscopy, Max-Born Strasse
2A, 12489 Berlin, Germany  G. S. Matthijs Jansen<EMAIL_ADDRESS>Stefan Mathias<EMAIL_ADDRESS>I. Physikalisches Institut, Georg-
August-Universität Göttingen, Friedrich-Hund-Platz 1, 37077 Göttingen, Germany

###### Abstract

The magneto-optical Kerr effect (MOKE) in the extreme ultraviolet (EUV) regime
has helped to elucidate some of the key processes that lead to the
manipulation of magnetism on ultrafast timescales. However, as we show in this
paper, the recently introduced spectrally-resolved analysis of such data can
lead to surprising experimental observations, which might cause
misinterpretations. Therefore, an extended analysis of the EUV magneto-optics
is necessary. Via experimental determination of the dielectric tensor, we find
here that the non-equilibrium excitation in an ultrafast magnetization
experiment can cause a rotation of the off-diagonal element of the dielectric
tensor in the complex plane. In direct consequence, the commonly analyzed
magneto-optic asymmetry may show time-dependent behaviour that is not directly
connected to the magnetic properties of the sample. We showcase such critical
observations for the case of ultrafast magnetization dynamics in Ni, and give
guidelines for the future analysis of spectrally-resolved magneto-optical data
and its comparison with theory.

##  I Introduction

With the advent and success of laser-based femtosecond element-specific M-edge
magneto-optical Kerr spectroscopy in 2009 [1], a very successful series of
experiments using this technique has helped to verify and elucidate a number
of key findings in ultrafast magnetism [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13]. As more powerful laser systems have become available over the years, this
experimental technique is becoming available in a growing number of
laboratories and becoming an important workhorse to study ultrafast
magnetization dynamics [14, 15, 16, 17, 18]. However, the introduction of a
new experimental capability also requires an ongoing check of the validity of
the collected data, and a crosscheck of the results achieved with
complementary experimental techniques. Such validation has been done, for
example, for the case of photo-induced ultrafast spin currents and the heavily
discussed relative delay of the Fe and Ni demagnetization in a Permalloy
sample [2, 19, 20, 14, 17, 21].

Currently, spectrally-resolved analysis of femtosecond transverse magneto-
optical Kerr effect (T-MOKE) data in the extreme-ultraviolet (EUV) is more
frequently used, for example for the verification of the so-called optical
intersite spin-transfer (OISTR) effect [22, 23, 8, 9, 7]. However, it has
already been recognized that the interpretation of such data asks for a more
detailed analysis of the collected T-MOKE asymmetry data [24, 25]. Similarly,
the comparison of magneto-optical spectroscopy data with state-of-the-art
time-dependent density functional theory (TDDFT) and similar theoretical
methods requires careful analysis [26, 27].

Figure 1: Increase, delay, or decrease of the spin dynamics? Very different
dynamics in the T-MOKE asymmetry are observed at 63.6 eV ($\pm 2\%$) photon
energy for slightly different angles-of-incidence (dark blue: 44°, blue:
44.8°, light blue: 45.9°). The measurement clearly illustrates that a direct
interpretation of T-MOKE asymmetry with ultrafast magnetization dynamics can
be highly problematic. Note that the solid lines serve as a guide to the eye.

The urgency for a sophisticated analysis of spectrally-resolved T-MOKE data
can be best introduced with an exemplary measurement of ultrafast
magnetization dynamics in the prototypical 3d ferromagnet Ni. Fig. 1 shows
transient T-MOKE asymmetry data, measured with our setup [17], and analyzed at
63.6 eV ($\pm 2\%$) EUV photon energy for slightly varying incidence angles.
Very disturbingly, the transient dynamics of the T-MOKE asymmetry shows
completely distinct behaviour. In particular, for the very same ultrafast
pump-probe experiment, all heavily discussed experimental signatures, i.e. an
increase, a delay, and a decrease in the T-MOKE asymmetry can be identified,
which have previously been used to identify the OISTR effect [8, 9, 7], the
influence of exchange scattering [2], and the typical demagnetization process
[1]. Having just the information of this particular measurement available, all
previous interpretations of T-MOKE data would be in question. In the
following, we will show how such critical T-MOKE data needs to be analyzed to
obtain reliable access to the true spin dynamics.

The overall topic of the paper is illustrated in Fig. 2. Usually, the main
quantity of interest is the global magnetization (top right) or the energy-
resolved magnetic moment, given by the difference in majority and minority
spins in the density of states (bottom right). In EUV T-MOKE experiments, the
aim is to probe the time-dependent magnetization and magnetic moment, however
neither magnetization (orange arrow) nor the energy-resolved magnetic moment
(red arrow) are directly measured. Rather, as an optical technique, T-MOKE
probes the dielectric tensor and is specifically sensitive to the off-axis
dielectric tensor element $\epsilon_{xy}$ [28]. Since the dielectric tensor
(including $\epsilon_{xy}$) can be calculated from TDDFT calculations of the
spin-resolved density of states [29, 30, 31, 27, 26], a time-resolved
extraction of $\epsilon_{xy}$ from T-MOKE data would allow for a quantitative
comparison of experimental T-MOKE data and theoretical calculations.

In our work, we therefore develop a robust and easy-to-implement method to
analyze transient dynamics of the dielectric tensor. With the help of this
analysis, we elucidate that the non-equilibrium excitation by the optical
pulse can lead to a rotation of the off-diagonal element of the dielectric
tensor in the complex plane. This rotational behaviour can lead to the
observed increase, delay, and decrease of the T-MOKE asymmetry as seen in Fig.
1, and these differing signals simply depend on the used measurement geometry
of the T-MOKE experiment, i.e. the angle of incidence of the EUV light. As
TDDFT is also able to provide transient dynamics of the dielectric tensor, we
find that a direct comparison of experiment and theory becomes possible via
such a dielectric tensor analysis from the data. In Ni, via comparison with
theory, we can show that the observed dynamics at early times of the pump
excitation (<50 fs) is dominantly driven by spin-conserving transitions in the
minority channel. Besides a comparison of the same quantity, our approach also
ensures that spectral broadening, multiple edges, and overlapping edges from
multiple elements in multi-component materials is properly taken into account.

Figure 2: Overview of the connections between experimental magneto-optical
signal, the off-diagonal tensor-element and the magnetization.

##  II Magneto-optical spectroscopy

###  II.1 Magneto-optical asymmetry in T-MOKE

Previous magneto-optical studies have attempted to make a direct connection
between the magneto-optical signal and the element-specific magnetization
properties of the sample after an ultrafast excitation. However, as shown
above and discussed in Fig. 2, the relation between the measurement signal in
a T-MOKE experiment and the magnetization is more complex, even in the
equilibrium case. At the microscopic scale, the interaction of light with a
material is given by the complex-valued dielectric tensor $\epsilon$, which
can be derived by counting the number of allowed optical transitions within
the the spin-resolved band structure [32, 33, 34, 27, 35]. For a magnetic
material, the imbalance between the different spin channels leads to off-
diagonal terms in the dielectric tensor, which couple light fields of
orthogonal polarization. For a typical (cubic) magnetic material that is
magnetized along the $z$-axis, the dielectric tensor is commonly expressed as

$\epsilon=\begin{pmatrix}\epsilon_{xx}{}&\epsilon_{xy}{}&0\\\
-\epsilon_{xy}{}&\epsilon_{xx}{}&0\\\ 0&0&\epsilon_{xx}\end{pmatrix}.$ (1)

Here, $\epsilon_{xx}$ can be directly related to the non-magnetic refractive
index, mostly written as

$\sqrt{\epsilon_{xx}}=n=1-\delta+i\beta,$ (2)

while the off-axis dielectric tensor element $\epsilon_{xy}$ describes the
magneto-optical response of the material.

Through the Fresnel equations, it is possible to express the signal in various
magneto-optical techniques in terms of the dielectric tensor components. For
example for XMCD, it is known that a signal can be extracted that is
proportional to $\mathrm{Re}(\epsilon_{xy})$ [27, 26]. For T-MOKE, the
reflectivity of a single vacuum/magnetic material interface can to good
accuracy be expressed as [36]

$R_{\uparrow/\downarrow}=|R_{0}|^{2}+|R_{m}\epsilon_{xy}{}|^{2}\pm\mathrm{Re}\\{2R_{0}^{*}R_{m}\epsilon_{xy}{}\\}$
(3)

where
$R_{0}=\frac{n\cos{\theta_{i}}-\cos{\theta_{t}}}{n\cos{\theta_{i}}+\cos{\theta_{t}}}$
and $R_{m}=\frac{sin{2\theta_{i}}}{n^{2}(n\cos{\theta_{i}}+\cos{\theta_{t}})}$
are the (complex-valued) non-magnetic and magnetic contributions to the
reflectivity, respectively. $\mathrm{Re}\\{...\\}$ indicates the real part,
and the incidence angle $\theta_{i}$ and refraction angle $\theta_{t}$ are
related by Snell’s law. The $\pm$ sign in Eq. 3 is directly linked to the
magnetization direction, where switching the magnetization direction also
switches the sign.

Based on Eq. (3), the commonly-used measurement strategy in EUV T-MOKE is to
measure the reflected intensity $I_{\uparrow/\downarrow}$ (which is
proportional to $R_{\uparrow/\downarrow})$, and subsequently calculate the
T-MOKE asymmetry for bulk magnetic material by [27, 24, 25, 37]

$A=\frac{I_{\uparrow}-I_{\downarrow}}{I_{\uparrow}+I_{\downarrow}}=\frac{2\text{Re}(R_{0}^{*}R_{m}\epsilon_{xy})}{|R_{0}|^{2}+|R_{m}\epsilon_{xy}|^{2}}.$
(4)

By alternately measuring $I_{\uparrow}$ and $I_{\downarrow}$, this allows to
efficiently filter out variations in the light source intensity. Then, it is
useful to consider the following assumptions: if
$|R_{m}\epsilon_{xy}{}|^{2}\ll|R_{0}|^{2}$ and the refractive index $n$ is
constant, then the transient asymmetry $A(t)$ can be normalized to a reference
asymmetry $A_{\rm ref}$ (commonly the T-MOKE asymmetry of the sample in
equilibrium), and the signal

$\frac{A(t)}{A_{\rm
ref}}=\frac{\mathrm{Re}(R_{0}^{*}R_{m}\epsilon_{xy}(t))}{\mathrm{Re}(R_{0}^{*}R_{m}\epsilon_{xy}^{\rm
ref})}$ (5)

is acquired. Now, a further assumption can be made to finally quantitatively
link the observed signal $A(t)$ to a change in $\epsilon_{xy}$: namely that
the angle of $\epsilon_{xy}$ in the complex plane does not change and only the
magnitude $|\epsilon_{xy}{}|$ decreases/increases. However, as will become
clear in the following analysis, the data that is presented in Fig. 1
unambiguously shows that this set of assumptions cannot hold.

###  II.2 Angle-dependence of the T-MOKE asymmetry

It is well known that the reflectivity of a sample, and more specifically also
the T-MOKE signal, depend strongly on the angle of incidence $\theta_{i}$ [2,
38, 10]. This is particularly true for the magneto-optical reflectivity close
to the Brewster angle, where a strong magneto-optical signal is observed as
the non-magnetic reflection is strongly suppressed. In order to understand
this behavior, it is useful to consider
$\epsilon_{xy}{}=\mathrm{Re}(\epsilon_{xy}){}+i\,\mathrm{Im}(\epsilon_{xy}){}$
as a vector in the complex plane: $\vec{\epsilon}_{xy}$. Approximating the
T-MOKE asymmetry to depend linearly on $\epsilon_{xy}$ (i.e., using
$|R_{0}|^{2}\gg|R_{m}\epsilon_{xy}|^{2}$ in Eq. (4)), we rewrite Eq. (4) as

$\begin{split}A(\epsilon_{xy}{})&\approx\frac{2}{|R_{0}|^{2}}\cdot\text{Re}(R_{0}^{*}R_{m}\epsilon_{xy})\\\
&=\frac{2}{|R_{0}|^{2}}\cdot[\mathrm{Re}(R_{0}R_{m}^{*})\cdot\mathrm{Re}(\epsilon_{xy}{})+\mathrm{Im}(R_{0}R_{m}^{*})\cdot\mathrm{Im}(\epsilon_{xy}{})]\\\
&=\vec{p}_{\theta}\cdot\vec{\epsilon}_{xy}{}=|\vec{p}_{\theta}||\vec{\epsilon}_{xy}{}|\cos(\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})).\end{split}$
(6)

This analysis shows that it is possible to interpret the T-MOKE asymmetry
$A(\vec{\epsilon}_{xy}{})$ as inner product of $\vec{\epsilon}_{xy}$ with a
probe vector $\vec{p}_{\theta}$. For the simple case of a single vacuum/magnet
interface, $\vec{p}_{\theta}$ is (up to a scaling factor) proportional to
$(\mathrm{Re}(R_{0}R_{m}^{*}),\mathrm{Im}(R_{0}R_{m}^{*}))$. More generally,
we define the probe vector as the derivative of the T-MOKE asymmetry with
respect to $\epsilon_{xy}$:

$\vec{p}_{\theta}{}=\left(\frac{\partial
A}{\partial(\mathrm{Re}(\epsilon_{xy}){})},\frac{\partial
A}{\partial(\mathrm{Im}(\epsilon_{xy}){})}\right).$ (7)

We note that since $\vec{p}_{\theta}$ depends only on the geometric and non-
magnetic properties of the sample, it can be calculated without (precise)
a-priori knowledge of $\epsilon_{xy}$. It is most important, however, to
realize that $\vec{p}_{\theta}$ rotates strongly in the complex plane as the
angle of incidence $\theta_{i}$ of the EUV light in the T-MOKE measurement
changes.

Figure 3: Angle-dependence of the static T-MOKE asymmetry for Ni. (a) The
observed T-MOKE asymmetry for the 21 nm Ni sample for three different
incidence angles $\theta_{i}$ close to 45°. (b) Schematic representation of
the probe vectors following Eq. 7 for the different incidence angles in (a),
and the $\epsilon_{xy}$ that was determined from these measurements. For the
calculation, we used the same sample composition and refractive index values
as in Section III.1.

This strong $\theta_{i}$ angle of incidence dependence is critical, because
the T-MOKE asymmetry is proportional to the inner product of the vectors
$\vec{\epsilon}_{xy}$ and the probe vector $\vec{p}_{\theta}$. If the angle
$\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})$ between these
vectors approaches 90°, a particularly strong dependence of the asymmetry on
the geometrical factors must be expected. This situation is illustrated in
Fig. 3a, where the measured T-MOKE asymmetry for three incidence angles close
to $\theta_{i}=$ 45° is shown. In the spectral region marked with a rectangle,
the T-MOKE asymmetry is strongly angle-of-incidence-dependent, and even flips
from positive to negative values. This can be understood by looking at the
schematic in Fig. 3b, which illustrates the positive to negative change of the
inner product of $\vec{p}_{\theta}{}$ and $\vec{\epsilon}_{xy}{}$ as a
function of the angle-of-incidence and therewith
$\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})$.

Another very important aspect for angles
$\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})\approx 90\degree$
is the realization that even small rotations of $\epsilon_{xy}$ in time-
resolved measurements would lead to sign-changes in the measured T-MOKE
asymmetry. Indeed, we will show that this is exactly the reason for the
disturbing data presented in Fig. 1, which was analyzed at a photon energy of
63.6 eV: here, a small transient rotation of $\epsilon_{xy}$ leads to very
different transient T-MOKE asymmetries for different angle-of-incidences, as
we will fully analyze below.

On the other hand, if
$\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})$ is much larger or
smaller than 90$\degree$, as is the case in the spectral region around 66 eV,
no such peculiar behaviour is expected. An analysis of transient T-MOKE
asymmetry around 66 eV for different angles of incidence consequently yields
perfectly identical results (Fig. 4), and the transient T-MOKE asymmetry now
reliably reflects the ultrafast magnetic behaviour.

In summary, we can already conclude that angles of
$\sphericalangle(\vec{p}_{\theta}{},\vec{\epsilon}_{xy}{})\approx 90\degree$
can lead to results in the time-resolved data that are not straightforward to
interpret. However, this particular situation can readily be identified, if
the asymmetry in a certain spectral range is highly sensitive to the EUV
angle-of-incidence and flips sign or approaches zero.

Figure 4: Transient magneto-optical asymmetry at 66.4 eV, i.e., at the Ni
resonance, yields identical dynamics for each angle.

###  II.3 Beyond the bulk approximation

In the previous analysis, we have focused specifically on a single
vacuum/magnet interface, as the Fresnel equations for such a case are
comparatively simple. However, the magnetic samples studied in ultrafast
magnetism, including also this study, are often best described as multilayer
structures. In particular, a capping layer is often included to protect the
magnetic material from the oxidizing environment; and if no capping layer is
included, commonly a native oxide layer forms. For such a sample, expressions
for the magnetization-dependent reflectivity can be derived using the transfer
matrix formalism [39, 40, 41]. In the present study, we have implemented the
transfer matrix formalism from Ref. 40 using a symbolic math package (SymPy)
[42] for Python to calculate the reflectivity, the T-MOKE asymmetry, and the
probe vectors $\vec{p}_{\theta}$ without relying on assumptions concerning the
strength of the magneto-optic response.

##  III Determination of dielectric tensor from T-MOKE data

The strong angle-dependence of the T-MOKE asymmetry can be leveraged in order
to extract the complex-valued off-diagonal dielectric tensor element
$\epsilon_{xy}$ [36, 43, 38]. Here, we present a unique approach to such
magneto-optical reflectometry where only a small range of incidence angles
needs to be measured for complete access to $\epsilon_{xy}$ at the given
photon energies. Specifically, this approach takes advantage of the strong
enhancement and dependence on the incidence angle of the T-MOKE asymmetry
around 45°, and furthermore makes use of the well-known non-magnetic
components of the dielectric tensor, which allows us to reliably calculate the
probe vectors. This approach provides two crucial advantages: the experimental
setup can be integrated into a typical EUV T-MOKE setup without requiring a
major overhaul, and since only a small number of incidence angles needs to be
measured, full femtosecond time-resolved magneto-optical spectroscopy is
possible with only a small (less than 5-fold) increase in the measurement
time.

In the following, we will first discuss the extraction of the static off-
diagonal dielectric tensor element, which is necessary in order to calibrate
certain experimental parameters, before we continue with the extraction of the
time-resolved dielectric tensor.

###  III.1 Extraction of the static off-diagonal dielectric tensor element

Several approaches exist to extract the magneto-optical dielectric tensor
element $\epsilon_{xy}$ at extreme ultraviolet wavelengths [26, 44, 43, 45,
38]. For thin samples that are best probed in reflection, incidence-angle-
dependent or polarization-dependent reflectivity measurements have
demonstrated their value [43, 45, 38]. As these techniques rely on
reflectivity measurements for linearly polarized light, they are commonly
implemented in laboratory-scale experiments based on high-harmonic generation.
A limiting factor for the implementation of these techniques, however, is that
they typically require a dedicated experimental geometry. Consequently, there
is a need for an $\epsilon_{xy}$ measurement technique that is compatible
with, and can be implemented in, currently existing EUV femtomagnetism
experiments. Here, we present the magneto-optical reflectometry method that we
implemented in our table-top femtosecond EUV T-MOKE spectroscopy setup [17].
This was made possible by the implementation of a motorized, non-magnetic and
UHV-compatible tip-tilt sample holder (SmarAct GmbH), which enabled a scan
range of 2.5° (see Fig. S1 in the Supplemental Material (SM)). As such, we
anticipate that the method can be rapidly implemented in many setups that are
currently being used for fixed-angle EUV T-MOKE.

Figure 5: Determination of a static $\epsilon_{xy}$. (a) T-MOKE asymmetry for
11 incidence angles close to 45°. Due to the high resolution of the
spectrometer, we were able to evaluate the T-MOKE asymmetry at two energies
for each high harmonic, indicated by points. The connecting lines serve as a
guide to the eye for the T-MOKE asymmetry. Note that only the relative angles
were directly determined from the sample, while the absolute angle was
retrieved from the analysis. (b) For comparison, we have calculated the real
and imaginary parts of $\epsilon_{xy}$ by TDDFT. We find a good agreement with
regard to the photon energy dependence, although TDDFT predicts an overall
stronger magneto-optical response.

In order to gain access to the off-axis dielectric tensor element of a
magnetized Ni thin film, we performed a series of T-MOKE asymmetry
measurements at 11 different incidence angles (shown in Fig. 5a). The sample
consists of a 21 nm Ni film that was deposited by sputtering on a Si3N4-coated
Si wafer. This thickness was chosen such that femtosecond optical pulses will
excite the sample homogeneously, while simultaneously being thick enough that
the reflection at the Ni/Si3N4 interface does not modify the observed T-MOKE
asymmetry strongly. The 100 nm Si3N4 layer is thick enough that no reflection
from the Si3N4/Si interface has to be accounted for. Finally, the Ni layer
possesses a thin, native Ni oxide layer on top, which reduces the strength of
the T-MOKE asymmetry. In line with literature [46, 47, 48], we set the
thickness of the NiO layer to 2 nm. In our analysis, we then use the transfer
matrix formalism and calculate expressions for the full three-layer system,
including the NiO capping layer, the Ni magnetic layer and the Si3N4 bottom
layer.

For our sample, the T-MOKE asymmetry depends on the complex-valued refractive
indices of Ni, NiO and Si3N4, the layer thicknesses, the incidence angle, and
the complex-valued $\epsilon_{xy}$ of Ni. Using the result of the transfer
matrix formalism as the model for the sample, the energy-resolved complex-
valued $\epsilon_{xy}$ can be determined from a set of angle-dependent T-MOKE
asymmetry measurements using a standard least-square fitting procedure. In
order to facilitate a reliable determination of $\epsilon_{xy}$ with few
measurements over a small angular range, we fix the complex-valued refractive
indices to literature values. Here, we retrieve the values for the dispersive
(real) part of the refractive index $\delta$ from CXRO [49], while we used
more recent measurements from Ref. 26 for the absorptive (imaginary) part
$\beta$. Using other sources for $\beta$ such as Refs. 44 or 49 leads to small
variations in the overall amplitude of $\epsilon_{xy}$, but does not affect
the photon-energy dependence significantly.

The best-fit values for the real and imaginary part of the off-diagonal tensor
element $\epsilon_{xy}$ in Ni are shown in Fig. 5b. As expected, the largest
values can be found around the M absorption edges of Ni around 66 eV (M3
edge). We also find a good qualitative agreement with previously published
data [44, 26]. Furthermore, the dielectric tensor can be accurately calculated
based on (time-dependent) density functional theory complemented by
calculations in the $GW$ framework to achieve an accurate description of the
3p core states [35, 27, 26, 50]. Here, we find a good agreement between
experiment and theory on the shape of the dielectric tensor, although theory
indicates an overall larger amplitude of $\epsilon_{xy}$. We attribute the
discrepancy in the amplitude to a common overestimation of the film-averaged
magnetic moment in the TDDFT calculation [25, 51]. In this regard, a better
match between experiment and theory, particularly for the spectral region just
above the edge, was recently also achieved by manually reducing the exchange
splitting [26].

###  III.2 Systematics and uncertainties

There are several experimental uncertainties that may influence the extracted
values for $\epsilon_{xy}$. These include statistical and systematical
effects. The statistical effects include shot-to-shot intensity fluctuations,
position-dependent detection efficiency on the camera and an uncertainty in
the relative angle determination. As we performed a large number of angle-
dependent measurements with a relatively long measurement time, however, we
estimate that the statistical errors are negligible compared to the systematic
ones. We have identified several possible sources of systematic errors, which
we analyse in the context of the present Ni sample:

First, the leading source of systematic errors is the calibration of the
incidence angle. From Fig. 3, it is clear that a change in the incidence angle
leads to a rotation of the probe vectors, as well as a change in the length.
Therefore, a systematic error in the angle determination leads to a rotation
of $\vec{\epsilon}_{xy}$ in the complex plane, as well as a change in
amplitude. Performing the full $\epsilon_{xy}$ reconstruction for different
angle calibrations, we find that a 0.5° calibration error in the incidence
angle typically leads to a rotation of $\vec{\epsilon}_{xy}$ by 10° and a
scaling of the amplitude by 10%. Considering the experimental setup, we
estimate that the absolute angle calibration is accurate to within 0.3°.

Second, quantitative determination of the T-MOKE asymmetry relies on an
accurate subtraction of the background signal in the spectrometer. This is
particularly critical when the detected EUV flux is low. To avoid errors due
to this effect, we have chosen to evaluate the data only at photon energies
around the peaks of the high-harmonic generation (HHG) spectrum. Nevertheless,
we note that close to the HHG cut-off energy ($\approx$ 70 eV, cf. Fig. S2 in
SI), the flux of each harmonic significantly decreases. At these photon
energies, an imperfect background correction can lead to a reduction of the
observed T-MOKE asymmetry and thereby an underestimation of the amplitude of
$\epsilon_{xy}$. For the data reported in this paper, we estimate this effect
to be negligible.

Third, it was already discussed that the NiO capping influences the observed
T-MOKE asymmetry. Unfortunately, no direct determination of the capping layer
thickness was possible. Therefore, we have analysed the influence of the
capping layer thickness on the retrieved $\epsilon_{xy}$ values. Within the
range of expected NiO thicknesses (1.5 to 2.5 nm), we find that a thicker
(thinner) NiO capping would reduce (increase) the size of the observed T-MOKE
asymmetry and therefore would lead to a slightly larger (smaller) amplitude of
$\epsilon_{xy}$. Here, 0.5 nm change corresponds to less than 10% change in
the amplitude. Also, a comparatively small rotation of the extracted
$\epsilon_{xy}$ can be observed. Overall, the effect due to uncertainty in the
capping layer thickness is less pronounced than the effect due to the angle of
incidence calibration.

Fourth, we note that the presented $\epsilon_{xy}$ reconstruction technique
depends on accurate values for the non-magnetic refractive indices of all
materials in the sample. However, by performing the full analysis for
different values of the refractive index of Ni (from Refs. 49, 44, 26), we
find only a minor effect on the shape and strength of $\epsilon_{xy}$. Related
to that, also an accurate calibration of the photon energy is necessary.
Within the experimental uncertainty of the photon energy calibration, which is
$<2\%$, we find no significant change in the reconstructed $\epsilon_{xy}$.

###  III.3 Probing the transient dielectric tensor

Next, we proceed to determine the time-resolved $\epsilon_{xy}$ during
optically-induced ultrafast demagnetization with sufficient time resolution to
trace the full demagnetization process and thereby provide an ideal basis for
comparison with theoretical methods that describe the dynamics of the
electron, spin and lattice degrees of freedom. Compared to the static case
that was previously discussed, we make two observations: First, as a
consequence of the optical excitation, it is not possible to fix the
refractive index to literature values; rather, the dynamical behaviour of
$\beta$ and $\delta$ (see Eq. (2)) must be extracted from the experimental
data. Second, the number of measured angles must be limited as much as
possible to facilitate the measurement of a larger number of pump-probe
delays. We find that these points can be addressed by choosing the
reflectivity $R_{\uparrow/\downarrow}$ (Eq. (3); more precisely its equivalent
from the transfer matrix formalism) as a starting point for the time-resolved
analysis, rather than the T-MOKE asymmetry (Eq. (4)). Instead of a single
value per photon energy and pump-probe delay, this yields two measurement
values (for two magnetization directions) which contain both magnetic and non-
magnetic contributions.

Figure 6:  Fitting of the time-resolved data to extract both $\epsilon_{xy}$
and $\beta$. (a, b) The measured (points) and reconstructed (line) transient
relative reflectivity $\Delta R_{\uparrow/\downarrow}(t)$ for opposite
magnetization directions (cf. Eq. (8)) during optically-induced magnetization
dynamics for photon energies just below (a) and close to (b) the Ni M-edge.
Figure 7: (a, b) Transient evolution of $\epsilon_{xy}$ after the optical
excitation. $\epsilon_{xy}$ rotates in the complex plane, because the real and
imaginary part do not change identically. The rotation of $\epsilon_{xy}$ is
of particular importance to understand the differences in the asymmetry time-
traces for different incidence angles below the resonance. (c) Transient
changes of the imaginary part of the refractive index ($\beta$) of Ni
retrieved from the angle-resolved EUV T-MOKE data. We find a strong change of
$\beta$ at $h\nu=63.9$ eV that is indicative for the strong excitation of
electrons.  Figure 8: (a) Transient evolution of $\vec{\epsilon}_{xy}$ for
selected times after the optical excitation. $\vec{\epsilon}_{xy}$ rotates in
the complex plane, as the real and imaginary part do not change identically.
(b) A rotation of $\vec{\epsilon}_{xy}$ in the complex plane can lead to an
increase, a decrease, or no effect on the magnetic asymmetry, which can be
understood from the alignment of $\vec{\epsilon}_{xy}$ and $\vec{p}_{\theta}$.
Here, we specifically consider the change in $\vec{\epsilon}_{xy}$ of Ni at 64
eV and 40 fs after the onset of demagnetization. At 44°, the rotation of
$\vec{\epsilon}_{xy}$ is such that the projection on $\vec{p}_{\theta}$ does
not change. Hence, no change in the magnetic asymmetry is observed. At 44.8°,
the rotation leads to an increase of the projection (magnetic asymmetry),
while at 45.9°, a pronounced decrease is observed. The change of the
projection from $\vec{\epsilon}_{xy}$ on $\vec{p}_{\theta}$ between unpumped
and at 40 fs is highlighted in yellow.

As the absolute reflectivity cannot be measured in our experiment, we consider
only the relative changes compared to the unpumped ($t<0$) case. From a
measurement series of the delay-dependent intensity
$I_{\uparrow/\downarrow}(t)$, we extract the relative reflectivity

$\Delta
R_{\uparrow/\downarrow}(t)=\frac{1}{2}\frac{R_{\uparrow/\downarrow}(t)}{R_{\uparrow/\downarrow}(t_{\rm
ref})}=\frac{I_{\uparrow/\downarrow}(t)}{I_{\uparrow}(t_{\rm
ref})+I_{\downarrow}(t_{\rm ref})},$ (8)

where $t_{\rm ref}$ indicates the reference time interval where the probe
arrives at the sample before the pump pulse. This yields a signal that
reflects the static asymmetry at times before the pump pulse and provides a
measure of the transient magneto-optical and non-magnetic reflectivity changes
at times after the pump pulse has arrived. Fig. 6a and b show such measurement
data for the same experimental situation that was presented in Fig. 1, namely
the optically-induced demagnetization of Ni.

The full data set contains the magnetization-dependent relative reflectivity
for the full high-harmonic spectrum at 3 incidence angles $\theta_{i}$ (44°,
44.8° and 45.9°, as determined from the static analysis). In order to extract
the time-dependent $\epsilon_{xy}$, we apply a similar fitting procedure as
was used in the static case: Each photon energy and each pump-probe delay are
considered independently. For each combination of these, our reconstruction
algorithm determines the optimal values for $\mathrm{Re}(\epsilon_{xy})$,
$\mathrm{Im}(\epsilon_{xy})$, $\beta$ and $\delta$.

We find that $\delta$ generally does not influence the predicted reflectivity
strongly, and consequently it cannot accurately be determined with a least-
square fitting routine. To address this, we employ a self-consistent two-step
approach: 1. keeping $\delta$ fixed, we use a least-square fitting to
determine $\mathrm{Re}(\epsilon_{xy})$, $\mathrm{Im}(\epsilon_{xy})$ and
$\beta$. 2. We use a Kramers-Kronig (KK) transform to determine $\delta$ [52].
Repeating steps 1 and 2 up to ten times has shown excellent convergence and a
good reconstruction of the measured values, as shown in Fig. 6a and b. We note
that although $\mathrm{Re}(\epsilon_{xy})$ and $\mathrm{Im}(\epsilon_{xy})$
are also connected by the KK relations, the implementation of such a transform
is challenging due to the sparsely sampled nature of our spectrum. We have
therefore achieved better results without linking $\mathrm{Re}(\epsilon_{xy})$
and $\mathrm{Im}(\epsilon_{xy})$ by KK.

##  IV Interpretation

###  IV.1 Rotation of $\epsilon_{xy}$

Having reconstructed the transient dielectric tensor including both the
magnetic ($\epsilon_{xy}$) and non-magnetic ($\epsilon_{xx}$) part, we proceed
with the interpretation of these results. In a first step, it is instructive
to return to the special case that was identified in Ni at 64 eV photon energy
(Fig. 1). Fig. 7a and b show the real and imaginary part of the off-diagonal
dielectric tensor element, respectively, as a function of time for two
selected energies (more data, including the extracted variation of $\delta$,
are shown in Fig. S5 in the SM). First, we recognize that the overall
magnitude $|\epsilon_{xy}{}|$ decreases over time to approximately 40% of its
original length after 600 fs. More interesting, however, we also see that
$\mathrm{Re}(\epsilon_{xy})$ and $\mathrm{Im}(\epsilon_{xy})$ do not quench
identically as a function of time, especially for $h\nu=$ 64 eV, where a
transient increase of $\mathrm{Re}(\epsilon_{xy})$ is observed. This means
that $\epsilon_{xy}$ must transiently rotate in the complex plane. This
rotation in the complex plane is visualized in Fig. 8a and is a key factor in
the explanation of the diverse transient effects that were observed in Ni at
64 eV (Fig. 1). However, we note that a rotation of $\epsilon_{xy}$ can also
be observed for many other photon energies, and does not necessarily have a
large impact on the T-MOKE asymmetry data, as is evident from the measurement
shown in Fig. 4. Therefore, a rotation of $\epsilon_{xy}$ alone is not
sufficient to explain the peculiar data of Fig. 1.

At 64 eV, we find that, in addition to the transient rotation of
$\epsilon_{xy}$, the probe vector $\vec{p}_{\theta}$ and the off-diagonal
dielectric tensor element $\epsilon_{xy}$ are close to orthogonal. This is
evident by the zero-crossing of the static magnetic asymmetry for different
angles-of-incidence (see Figs. 3 and 5). This situation does not occur at the
other photon energies that we have observed, and it provides the second key to
the explanation of the data in Fig. 1. The T-MOKE asymmetry can be
approximated by the projection of $\epsilon_{xy}$ on the probe vectors
$\vec{p}_{\theta}$. In Fig. 8b, we now apply this method again to visualize
how the experimentally-determined transient rotation of $\epsilon_{xy}$ can
influence the measured T-MOKE asymmetry. We find that changes of the
orientation of $\epsilon_{xy}$ can lead to dramatic effects, which furthermore
depend strongly on the precise angle
$\sphericalangle(\vec{p},\vec{\epsilon}_{xy}{})$, and in particular if this
angle is more or less than 90$\degree$. We can readily construct scenarios
that predict a delay, a rapid increase and a rapid decrease in the T-MOKE
asymmetry - exactly as was observed for Ni (cf. yellow areas in Fig. 8b).
Furthermore, we note that a complete reversal of the T-MOKE asymmetry might
also occur. A naive interpretation of the T-MOKE asymmetry might confuse this
observation for a reversal of the magnetic moment, which we emphasize is not
the case here. Thus, we conclude that in experiment, where the transient
change of the T-MOKE asymmetry is always normalized to its value before the
pump excitation, even very small angle changes of $\epsilon_{xy}$ can have a
huge impact on the qualitative trend of the transient T-MOKE asymmetry data.

Since the T-MOKE asymmetry depends on the relative angle
$\sphericalangle(\vec{p},\vec{\epsilon}_{xy}{})$, it is clear that not just a
rotation of $\epsilon_{xy}$, but also a rotation of $\vec{p}_{\theta}$ might
lead to unexpected dynamics in the time-resolved T-MOKE asymmetry signal.
Since such rotations can arise due to changes of the refractive index, they
are commonly referred to as non-magnetic artifacts in the ultrafast magnetism
community [53, 24]. However, we note that in our time-resolved analysis,
$\beta$ (Fig. 7c) and $\delta$ (Fig. S5 in SM) are reconstructed in addition.
Therefore, this analysis allows to separate the rotation of $\epsilon_{xy}$
from any rotation in $\vec{p}_{\theta}$. Equivalently, this analysis separates
the magnetic and non-magnetic effects. For Ni at 64 eV, we find that the
$\vec{p}_{\theta}$ vectors change insignificantly in comparison to
$\epsilon_{xy}$, indicating that the angle-dependent T-MOKE asymmetry changes
are dominated by the rotation of $\epsilon_{xy}$.

In summary, we find that the optically-induced non-equilibrium excitation in
Ni leads to a transient rotation of the off-diagonal element of the dielectric
tensor. In consequence, we show that the T-MOKE asymmetry may exhibit
increased, decreased, and delayed behavior, which must not be directly
interpreted as transient dynamics of the magnetization of the sample.

###  IV.2 Comparison to theory

Before we carry out a direct comparison to theory, it is instructive to have a
qualitative look at the resonant M-edge transitions that are probed in
experiment with EUV T-MOKE spectroscopy. Fig. 9a shows a schematic of the
spin-split 3d and 4s density of states of Ni and the spin-split Ni 3p core
levels, for which we include the approximate intrinsic linewidth broadening.
As can be seen from this schematic, the spin-split 3p core levels overlap and
cover an energy range of $\approx$5 eV, which is comparable to the energy
range of the full valence and conduction band structure of Ni. Therefore, a
specific EUV energy (pink arrow in Fig. 9a) does not only probe a specific
energy within the spin-split DOS, but an extended region of several
electronvolts. In consequence, the collected T-MOKE asymmetry is strongly
broadened, and it is not straightforward to identify spectrally-resolved
dynamics in the T-MOKE asymmetry or even the extracted dielectric tensor with
occupation changes or band renormalizations in the electronic structure of the
investigated material.

However, if we look at our TDDFT calculations in Fig. 9b, such a comparison
seems necessary at first. For 1.2 eV and 47 fs pump pulses, we find that the
time-resolved change in minority and majority occupation of the DOS exhibits
spectrally very distinct dynamics. For example, because of the large
unoccupied DOS in the minority channel of Ni just above the Fermi-level (cf.
Fig. 9a), Fig. 9b shows that pumping with 1.2 eV leads to a peaked increase of
minority spins in a $\approx$300 meV spectral region above the Fermi level. In
other words, we see a strong minority inter-energy transfer of spins from
below to above the Fermi-level. In the majority channel, we also pump
electrons from below to above the Fermi-level, but much less efficient,
because there are much less empty states available for the transition. In
total, this means that the optical excitation leads to a magnetic moment
increase below the Fermi-level (loss of minority electrons), and an overall
magnetic moment decrease (gain of minority electrons) just above the Fermi-
level. However, all of these distinct spectral signatures will be broadened in
experiment due to the large linewidth of the Ni 3p core levels.

Figure 9: Femtosecond spin dynamics from TDDFT, compared to experiment. (a)
Spin-resolved density of states from density functional theory and the
equilibrium occupation at 300 K for the 3p, 3d and 4s states in Ni. Due to the
exchange splitting, significantly more minority states (upper part) are
unoccupied (unshaded region around $E_{F}$), thereby allowing for more optical
transitions (purple arrow). (b) As seen in the population change at 40 fs, the
optical excitation with 1.2 eV photons leads to a strong redistribution of the
population in the minority channel (light blue), populating empty states at
0-0.5 eV above $E_{F}$ and creating empty states below $E_{F}$. In comparison,
the majority channel (dark blue) is less affected. (c) The redistribution of
spins and charge carriers leads to a modification of the magneto-optical
response ($\epsilon_{xy}$). Depending on the position with respect to the
M-edge photon energy $E_{M}$, the spectral dynamics of
$\mathrm{Re}(\epsilon_{xy})$ show regions with a strong relative decrease of
$\mathrm{Re}(\epsilon_{xy})$ (indicated with a red arrow) but also regions
with a relative increase of $\mathrm{Re}(\epsilon_{xy})$ (blue arrow) or a
delayed onset of dynamics (grey arrow). (d) The calculations can be directly
compared to experiment by evaluating $\mathrm{Re}(\epsilon_{xy})$ as a
function of time. Here, we observe that the predicted relative increase in
$\mathrm{Re}(\epsilon_{xy})$ is confirmed from experiment (see Fig. 6a). The
time axis of experiment and theory were shifted according to each, as
visualized by the electric field of the pulse used for the theory
calculations.

We can overcome this problem by directly calculating the transient changes in
the dielectric tensor, which takes all EUV transitions into account and
moreover is a quantity that we now can directly compare with experiment.
Specifically, we focus on the real part of $\epsilon_{xy}$, which can be
related to the spin polarization of the unoccupied states. Fig. 9c shows the
theoretical transient dynamics of $\mathrm{Re}(\epsilon_{xy})$ in the
corresponding energy range. First, we recognize that the spectrally distinct
dynamics as seen in the transient occupation changes in Fig. 9b are completely
smeared out. Nevertheless, we still find broad energetic regions where the
inter-energy spin transfer as seen in Fig. 9c can be verified: Below the
energy marked with the grey arrow in Fig. 9b, $\mathrm{Re}(\epsilon_{xy})$
shows an ultrafast relative increase, and an ultrafast decrease for energies
above. If $\mathrm{Re}(\epsilon_{xy})$ would be extracted exactly at the
energy of the green arrow, we would expect a delayed behavior in the dynamics.

Having this theoretical result on transient dynamics of
$\mathrm{Re}(\epsilon_{xy})$, we now carry out a direct comparison with
experiment, where we were able to extract $\mathrm{Re}(\epsilon_{xy})$ at the
energies marked with blue- and red-shaded areas in Fig. 9c. Figure 9d shows
this comparison of time-resolved dynamics of $\mathrm{Re}(\epsilon_{xy})$ for
theory (solid lines) and experiment (data points). Clearly, the predicted
relative increase and decrease in $\mathrm{Re}(\epsilon_{xy})$ after optical
pumping can be confirmed. We also find that for longer time-delays >100 fs,
the experimental data shows a further reduction of
$\mathrm{Re}(\epsilon_{xy})$, while the theory data stays constant. This is to
be expected, because TDDFT does not take all possible spin-flip scattering
processes into account, which in experiment lead to the overall
demagnetization of the sample on timescales larger than 100 fs.

In summary, TDDFT predicts an OISTR-like process, i.e. an optically-driven
inter-energy spin transfer similar to the inter-site spin transfer in the
usual OISTR process. This pumping of spins happens predominantly in the
minority channel and leads to distinct spectrally-dependent magnetization
increase and decrease below and above the Fermi-level, respectively. Via a
direct calculation of the real part of the off-diagonal element of the
dielectric tensor, $\mathrm{Re}(\epsilon_{xy})$, we are able to pinpoint the
inter-energy transfer in the transient dynamics of
$\mathrm{Re}(\epsilon_{xy})$. As $\mathrm{Re}(\epsilon_{xy})$ can be directly
extracted from our experimental data, we are able to unambiguously verify the
optically-driven inter-energy spin-transfer process in Ni.

##  V Conclusion

In conclusion, we have discussed an intriguing effect in EUV T-MOKE magnetism
studies, where different transient dynamics were observed under almost
identical experimental conditions. This observation conclusively illustrates
that it is not always possible to directly compare time-resolved T-MOKE data
with time-resolved calculations of the spin-resolved density of states. Here,
we show that a quantitative comparison with TDDFT can be achieved by
extracting the transient dynamics of the off-axis dielectric tensor element
$\epsilon_{xy}$.

We have presented a robust technique to retrieve $\epsilon_{xy}$ from
experimental T-MOKE data with full femtosecond time resolution at little
experimental cost. The data that we have achieved solves the controversy that
slightly different incidence angles lead to dramatically different dynamics in
the T-MOKE asymmetry. Even more, our technique allows to directly reconstruct
the magnetic and non-magnetic parts of the refractive index. Studying the
prototypical case of femtosecond demagnetization in Ni, we show that this data
is ideal for a quantitative analysis and comparison with TDDFT calculations
and allows to trace the optically-induced spin and charge dynamics in
exceptional detail. We want to emphasize that besides a comparison of the same
quantity, i.e. $\epsilon_{xy}$, this approach also ensures that spectral
broadening, multiple edges, and overlapping edges from multiple elements in
multi-component materials is properly taken into account.

Beyond this exemplary case, we expect that femtosecond $\epsilon_{xy}$
spectroscopy will be especially valuable to shed light on the recently
discovered OISTR effect and similar femtosecond optically-induced spin
dynamics. In Ref. 54, we perform such a study, and discuss the implications
for OISTR, which was, after all, first experimentally evidenced by EUV T-MOKE.

##  VI ACKNOWLEDGEMENTS

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) - project IDs 399572199 and 432680300/SFB 1456. G.S.M.J.
acknowledges financial support by the Alexander von Humboldt Foundation. S.S.
and J.K.D. would like to thank the DFG for funding through project-ID
328545488 TRR227 (project A04).

## References

  * La-O-Vorakiat  _et al._ [2009] C. La-O-Vorakiat, M. Siemens, M. M. Murnane, H. C. Kapteyn, S. Mathias, M. Aeschlimann, P. Grychtol, R. Adam, C. M. Schneider, J. M. Shaw, H. Nembach, and T. J. Silva, Ultrafast Demagnetization Dynamics at the M Edges of Magnetic Elements Observed Using a Tabletop High-Harmonic Soft X-Ray Source, Phys. Rev. Lett. 103, 257402 (2009).
  * Mathias  _et al._ [2012] S. Mathias, C. La-O-Vorakiat, P. Grychtol, P. Granitzka, E. Turgut, J. M. Shaw, R. Adam, H. T. Nembach, M. E. Siemens, S. Eich, _et al._ , Probing the timescale of the exchange interaction in a ferromagnetic alloy, Proceedings of the National Academy of Sciences 109, 4792 (2012).
  * Pfau  _et al._ [2012] B. Pfau, S. Schaffert, L. Müller, C. Gutt, A. Al-Shemmary, F. Büttner, R. Delaunay, S. Düsterer, S. Flewett, R. Frömter, _et al._ , Ultrafast optical demagnetization manipulates nanoscale spin structure in domain walls, Nature communications 3, 1100 (2012).
  * Rudolf  _et al._ [2012] D. Rudolf, C. La-O-Vorakiat, M. Battiato, R. Adam, J. M. Shaw, E. Turgut, P. Maldonado, S. Mathias, P. Grychtol, H. T. Nembach, _et al._ , Ultrafast magnetization enhancement in metallic multilayers driven by superdiffusive spin current, Nature communications 3, 1037 (2012).
  * Vodungbo  _et al._ [2012] B. Vodungbo, J. Gautier, G. Lambert, A. B. Sardinha, M. Lozano, S. Sebban, M. Ducousso, W. Boutu, K. Li, B. Tudu, _et al._ , Laser-induced ultrafast demagnetization in the presence of a nanoscale magnetic domain network, Nature communications 3, 999 (2012).
  * Turgut  _et al._ [2013] E. Turgut, J. M. Shaw, P. Grychtol, H. T. Nembach, D. Rudolf, R. Adam, M. Aeschlimann, C. M. Schneider, T. J. Silva, M. M. Murnane, _et al._ , Controlling the competition between optically induced ultrafast spin-flip scattering and spin transport in magnetic multilayers, Physical review letters 110, 197201 (2013).
  * Willems  _et al._ [2020] F. Willems, C. von Korff Schmising, C. Strüber, D. Schick, D. W. Engel, J. K. Dewhurst, P. Elliott, S. Sharma, and S. Eisebitt, Optical inter-site spin transfer probed by energy and spin-resolved transient absorption spectroscopy, Nat Commun 11, 871 (2020).
  * Hofherr  _et al._ [2020] M. Hofherr, S. Häuser, J. K. Dewhurst, P. Tengdin, S. Sakshath, H. T. Nembach, S. T. Weber, J. M. Shaw, T. J. Silva, H. C. Kapteyn, M. Cinchetti, B. Rethfeld, M. M. Murnane, D. Steil, B. Stadtmüller, S. Sharma, M. Aeschlimann, and S. Mathias, Ultrafast optically induced spin transfer in ferromagnetic alloys, Science Advances 6, eaay8717 (2020).
  * Tengdin  _et al._ [2020] P. Tengdin, C. Gentry, A. Blonsky, D. Zusin, M. Gerrity, L. Hellbrück, M. Hofherr, J. Shaw, Y. Kvashnin, E. K. Delczeg-Czirjak, M. Arora, H. Nembach, T. J. Silva, S. Mathias, M. Aeschlimann, H. C. Kapteyn, D. Thonig, K. Koumpouras, O. Eriksson, and M. M. Murnane, Direct light–induced spin transfer between different elements in a spintronic Heusler material via femtosecond laser excitation, Science Advances 6, eaaz1100 (2020).
  * Hennecke  _et al._ [2022] M. Hennecke, D. Schick, T. Sidiropoulos, F. Willems, A. Heilmann, M. Bock, L. Ehrentraut, D. Engel, P. Hessing, B. Pfau, _et al._ , Ultrafast element-and depth-resolved magnetization dynamics probed by transverse magneto-optical Kerr effect spectroscopy in the soft x-ray range, Physical Review Research 4, L022062 (2022).
  * Kfir  _et al._ [2017] O. Kfir, S. Zayko, C. Nolte, M. Sivis, M. Möller, B. Hebler, S. S. P. K. Arekapudi, D. Steil, S. Schäfer, M. Albrecht, O. Cohen, S. Mathias, and C. Ropers, Nanoscale magnetic imaging using circularly polarized high-harmonic radiation, Science Advances 3, eaao4641 (2017).
  * Zayko  _et al._ [2020] S. Zayko, O. Kfir, M. Heigl, M. Lohmann, M. Sivis, M. Albrecht, and C. Ropers, Ultrafast high-harmonic nanoscopy of magnetization dynamics., Nature communications 12, 6337 (2020).
  * Ryan  _et al._ [2023] S. A. Ryan, P. C. Johnsen, M. F. Elhanoty, A. Grafov, N. Li, A. Delin, A. Markou, E. Lesne, C. Felser, O. Eriksson, H. C. Kapteyn, O. Grånäs, and M. M. Murnane, Optically controlling the competition between spin flips and intersite spin transfer in a Heusler half-metal on sub-100 fs timescales, arXiv (2023), 2305.16455 .
  * Jana  _et al._ [2017] S. Jana, J. A. Terschlüsen, R. Stefanuik, S. Plogmaker, S. Troisi, R. S. Malik, M. Svanqvist, R. Knut, J. Söderström, and O. Karis, A setup for element specific magnetization dynamics using the transverse magneto-optic Kerr effect in the energy range of 30-72 eV, Review of Scientific Instruments 88, 033113 (2017).
  * Hofherr  _et al._ [2018] M. Hofherr, S. Moretti, J. Shim, S. Häuser, N. Y. Safonova, M. Stiehl, A. Ali, S. Sakshath, J. W. Kim, D. H. Kim, H. J. Kim, J. I. Hong, H. C. Kapteyn, M. M. Murnane, M. Cinchetti, D. Steil, S. Mathias, B. Stadtmüller, M. Albrecht, D. E. Kim, U. Nowak, and M. Aeschlimann, Induced versus intrinsic magnetic moments in ultrafast magnetization dynamics, Physical Review B 98, 174419 (2018).
  * Yao  _et al._ [2020a] K. Yao, F. Willems, C. von Korff Schmising, C. Strüber, P. Hessing, B. Pfau, D. Schick, D. Engel, K. Gerlinger, M. Schneider, _et al._ , A tabletop setup for ultrafast helicity-dependent and element-specific absorption spectroscopy and scattering in the extreme ultraviolet spectral range, Review of Scientific Instruments 91, 093001 (2020a).
  * Möller  _et al._ [2021] C. Möller, H. Probst, J. Otto, K. Stroh, C. Mahn, S. Steil, V. Moshnyaga, G. S. M. Jansen, D. Steil, and S. Mathias, Ultrafast element-resolved magneto-optics using a fiber-laser-driven extreme ultraviolet light source, Review of Scientific Instruments 92, 065107 (2021).
  * Johnsen  _et al._ [2023] P. C. Johnsen, S. A. Ryan, C. Gentry, A. Grafov, H. Kapteyn, and M. Murnane, A beamline for ultrafast extreme ultraviolet magneto-optical spectroscopy in reflection near the shot noise limit, Review of Scientific Instruments 94 (2023).
  * Günther  _et al._ [2014] S. Günther, C. Spezzani, R. Ciprian, C. Grazioli, B. Ressel, M. Coreno, L. Poletto, P. Miotti, M. Sacchi, G. Panaccione, _et al._ , Testing spin-flip scattering as a possible mechanism of ultrafast demagnetization in ordered magnetic alloys, Physical Review B 90, 180407 (2014).
  * Yao  _et al._ [2020b] K. Yao, F. Willems, C. von Korff Schmising, I. Radu, C. Strüber, D. Schick, D. Engel, A. Tsukamoto, J. Dewhurst, S. Sharma, and others, Distinct spectral response in M-edge magnetic circular dichroism, Physical Review B 102, 100405 (2020b).
  * Jana  _et al._ [2022] S. Jana, R. Knut, S. Muralidhar, R. S. Malik, R. Stefanuik, J. Åkerman, O. Karis, C. Schüßler-Langeheine, and N. Pontius, Experimental confirmation of the delayed Ni demagnetization in FeNi alloy, Applied Physics Letters 120, 102404 (2022).
  * Dewhurst  _et al._ [2018a] J. K. Dewhurst, P. Elliott, S. Shallcross, E. K. U. Gross, and S. Sharma, Laser-Induced Intersite Spin Transfer, Nano Letters 18, 1842 (2018a).
  * Siegrist  _et al._ [2019] F. Siegrist, J. A. Gessner, M. Ossiander, C. Denker, Y.-P. Chang, M. C. Schröder, A. Guggenmos, Y. Cui, J. Walowski, U. Martens, J. K. Dewhurst, U. Kleineberg, M. Münzenberg, S. Sharma, and M. Schultze, Light-wave dynamic control of magnetism, Nature 571, 240 (2019).
  * La-O-Vorakiat  _et al._ [2012] C. La-O-Vorakiat, E. Turgut, C. A. Teale, H. C. Kapteyn, M. M. Murnane, S. Mathias, M. Aeschlimann, C. M. Schneider, J. M. Shaw, H. T. Nembach, and T. J. Silva, Ultrafast Demagnetization Measurements Using Extreme Ultraviolet Light: Comparison of Electronic and Magnetic Contributions, Physical Review X 2, 011005 (2012).
  * Jana  _et al._ [2020] S. Jana, R. S. Malik, Y. O. Kvashnin, I. L. Locht, R. Knut, R. Stefanuik, I. Di Marco, A. Yaresko, M. Ahlberg, J. Åkerman, and others, Analysis of the linear relationship between asymmetry and magnetic moment at the M edge of 3 d transition metals, Physical Review Research 2, 013180 (2020).
  * Willems  _et al._ [2019] F. Willems, S. Sharma, C. v. K. Schmising, J. Dewhurst, L. Salemi, D. Schick, P. Hessing, C. Strüber, W. Engel, and S. Eisebitt, Magneto-optical functions at the 3 p resonances of Fe, Co, and Ni: Ab initio description and experiment, Physical review letters 122, 217202 (2019).
  * Dewhurst  _et al._ [2020] J. Dewhurst, F. Willems, P. Elliott, Q. Li, C. von Korff Schmising, C. Strüber, D. Engel, S. Eisebitt, and S. Sharma, Element specificity of transient extreme ultraviolet magnetic dichroism, Physical Review Letters 124, 077203 (2020).
  * Erskine and Stern [1975] J. L. Erskine and E. A. Stern, Calculation of the M2,3 magneto-optical absorption spectrum of ferromagnetic nickel, Phys. Rev. B 12, 5016 (1975).
  * Runge and Gross [1984] E. Runge and E. K. U. Gross, Density-Functional Theory for Time-Dependent Systems, Phys. Rev. Lett. 52, 997 (1984).
  * Van Leeuwen [2001] R. Van Leeuwen, Key concepts in time-dependent density-functional theory, Int. J. Mod. Phys. B 15, 1969 (2001).
  * Sharma  _et al._ [2014] S. Sharma, J. K. Dewhurst, and E. K. U. Gross, Optical Response of Extended Systems Using Time-Dependent Density Functional Theory (Springer, Berlin, Heidelberg, 2014) pp. 235–257.
  * Oppeneer  _et al._ [1992] P. Oppeneer, T. Maurer, J. Sticht, and J. Kübler, Ab initio calculated magneto-optical Kerr effect of ferromagnetic metals: Fe and Ni, Physical Review B 45, 10924 (1992).
  * Oppeneer [2001] P. Oppeneer, Magneto-optical Kerr spectra, Handbook of Magnetic Materials 13, 229 (2001).
  * Kuneš  _et al._ [2001] J. Kuneš, P. Oppeneer, H.-C. Mertins, F. Schäfers, A. Gaupp, W. Gudat, and P. Novák, X-ray Faraday effect at the L 2, 3 edges of Fe, Co, and Ni: theory and experiment, Physical Review B 64, 174417 (2001).
  * Krieger  _et al._ [2015] K. Krieger, J. Dewhurst, P. Elliott, S. Sharma, and E. Gross, Laser-induced demagnetization at ultrashort time scales: Predictions of TDDFT, Journal of chemical theory and computation 11, 4870 (2015).
  * Zusin  _et al._ [2018a] D. Zusin, P. M. Tengdin, M. Gopalakrishnan, C. Gentry, A. Blonsky, M. Gerrity, D. Legut, J. M. Shaw, H. T. Nembach, T. Silva, _et al._ , Direct measurement of the static and transient magneto-optical permittivity of cobalt across the entire M-edge in reflection geometry by use of polarization scanning, Physical Review B 97, 024433 (2018a).
  * Mathias  _et al._ [2013] S. Mathias, J. M. Shaw, E. Turgut, P. Grychtol, R. Adam, D. Rudolf, H. T. Nembach, T. J. Silva, M. Aeschlimann, C. M. Schneider, _et al._ , Ultrafast element-specific magnetization dynamics of complex magnetic materials on a table-top, Journal of Electron Spectroscopy and Related Phenomena 189, 164 (2013).
  * Turgut  _et al._ [2016] E. Turgut, D. Zusin, D. Legut, K. Carva, R. Knut, J. M. Shaw, C. Chen, Z. Tao, H. T. Nembach, T. J. Silva, and others, Stoner versus Heisenberg: Ultrafast exchange reduction and magnon generation during laser-induced demagnetization, Physical Review B 94, 220408 (2016).
  * Zak  _et al._ [1990] J. Zak, E. Moog, C. Liu, and S. Bader, Universal approach to magneto-optics, Journal of Magnetism and Magnetic Materials 89, 107 (1990).
  * Zak  _et al._ [1991] J. Zak, E. Moog, C. Liu, and S. Bader, Magneto-optics of multilayers with arbitrary magnetization directions, Physical Review B 43, 6423 (1991).
  * Schick  _et al._ [2014] D. Schick, A. Bojahr, M. Herzog, R. Shayduk, C. von Korff Schmising, and M. Bargheer, udkm1Dsim—A simulation toolkit for 1D ultrafast dynamics in condensed matter, Computer Physics Communications 185, 651 (2014).
  * Meurer  _et al._ [2017] A. Meurer, C. P. Smith, M. Paprocki, O. Čertík, S. B. Kirpichev, M. Rocklin, A. Kumar, S. Ivanov, J. K. Moore, S. Singh, T. Rathnayake, S. Vig, B. E. Granger, R. P. Muller, F. Bonazzi, H. Gupta, S. Vats, F. Johansson, F. Pedregosa, M. J. Curry, A. R. Terrel, v. Roučka, A. Saboo, I. Fernando, S. Kulal, R. Cimrman, and A. Scopatz, SymPy: symbolic computing in Python, PeerJ Computer Science 3, e103 (2017).
  * Höchst  _et al._ [1997] H. Höchst, D. Rioux, D. Zhao, and D. L. Huber, Magnetic linear dichroism effects in reflection spectroscopy: A case study at the Fe M2,3 edge, Journal of Applied Physics 81, 7584 (1997).
  * Valencia  _et al._ [2006] S. Valencia, A. Gaupp, W. Gudat, H.-C. Mertins, P. M. Oppeneer, D. Abramsohn, and C. M. Schneider, Faraday rotation spectra at shallow core levels: 3p edges of Fe, Co, and Ni, New Journal of Physics 8, 254 (2006).
  * Zusin  _et al._ [2018b] D. Zusin, P. M. Tengdin, M. Gopalakrishnan, C. Gentry, A. Blonsky, M. Gerrity, D. Legut, J. M. Shaw, H. T. Nembach, T. J. Silva, P. M. Oppeneer, H. C. Kapteyn, and M. M. Murnane, Direct measurement of the static and transient magneto-optical permittivity of cobalt across the entire M-edge in reflection geometry by use of polarization scanning, Phys. Rev. B 97, 024433 (2018b).
  * Uchikoshi  _et al._ [1994] T. Uchikoshi, Y. Sakka, M. Yoshitake, and K. Yoshihara, A study of the passivating oxide layer on fine nickel particles, Nanostructured Materials 4, 199 (1994).
  * Zink  _et al._ [2016] B. L. Zink, M. Manno, L. O’Brien, J. Lotze, M. Weiler, D. Bassett, S. J. Mason, S. T. B. Goennenwein, M. Johnson, and C. Leighton, Efficient spin transport through native oxides of nickel and permalloy with platinum and gold overlayers, Phys. Rev. B 93, 184401 (2016).
  * Wang  _et al._ [2011] C.-M. Wang, D. R. Baer, S. M. Bruemmer, M. H. Engelhard, M. E. Bowden, J. A. Sundararajan, and Y. Qiang, Microstructure of the Native Oxide Layer on Ni and Cr-Doped Ni Nanoparticles, Journal of Nanoscience and Nanotechnology 11, 8488 (2011).
  * Henke  _et al._ [1993] B. L. Henke, E. M. Gullikson, and J. C. Davis, X-Ray Interactions: Photoabsorption, Scattering, Transmission, and Reflection at E = 50-30,000 eV, Z = 1-92, Atomic Data and Nuclear Data Tables 54, 181 (1993).
  * Dewhurst  _et al._ [2018b] J. K. Dewhurst, S. Sharma, and et al., elk.sourceforge.net (Jan. 14 2018b).
  * Gang  _et al._ [2018] S.-g. Gang, R. Adam, M. Plötzing, M. von Witzleben, C. Weier, U. Parlak, D. E. Bürgler, C. M. Schneider, J. Rusz, P. Maldonado, and P. M. Oppeneer, Element-selective investigation of femtosecond spin dynamics in NiPd magnetic alloys using extreme ultraviolet radiation, Phys. Rev. B 97, 064412 (2018).
  * Watts [2014] B. Watts, Calculation of the Kramers-Kronig transform of X-ray spectra by a piecewise Laurent polynomial method, Opt. Express, OE 22, 23628 (2014).
  * Koopmans  _et al._ [2003] B. Koopmans, M. van Kampen, and W. J. M. de Jonge, Experimental access to femtosecond spin dynamics, Journal of Physics: Condensed Matter 15, S723 (2003).
  * Möller  _et al._ [2023] C. Möller, H. Probst, G. S. M. Jansen, M. Schumacher, M. Brede, J. K. Dewhurst, M. Reutzel, D. Steil, S. Sharma, and S. Mathias, Verification of ultrafast spin transfer effects in FeNi alloys (2023), arXiv:2306.02793 [cond-mat].
  * Dewhurst  _et al._ [2016] J. K. Dewhurst, K. Krieger, S. Sharma, and E. K. Gross, An efficient algorithm for time propagation as applied to linearized augmented plane wave method., Comput. Phys. Commun. 209, 92 (2016).

##  VII Supplemental Material

##  VIII Experimental setup and analysis details

The experimental setup used for the determination of the time-resolved
dielectric tensor is based on the EUV T-MOKE setup that was described in Ref.
[17]. We pumped the samples with a $47\pm 5$ fs pulse (Gauss FWHM) with a
photon energy of 1.2 eV. The absorbed fluence for the measurements was $0.8\pm
0.2$ $\nicefrac{{\text{mJ}}}{{\text{cm}^{2}}}$. The reflected 100 kHz EUV
probe beam spans energies between $30-72$ eV.

Figure S1: Schematic of the T-MOKE experiment. A small, non-magnetic tip-tilt
holder enables repeatable control of the incidence angle in a range of 2.5°
around 45°.

For the data acquisition at different angles of incidence (see Fig. S1), an
accurate and repeatable control of the incidence angle was ensured by mounting
the sample on a small non-magnetic, UHV-compatible tip-tilt stage (SmarAct
GmbH, STT-12.7-UHVT-NM, Fig. S1).

Figure S2:  Typical high harmonic spectrum after the reflection from the Ni
thin film for opposite magnetization directions. The discrete nature of the
spectrum of odd harmonics of the fundamental beam is clearly visible. The
magneto optical response is largest around the Ni resonance at $\approx$66 eV,
which is visible by the large difference in intensity for opposite
magnetization directions.

After reflection from the sample, the EUV light is analyzed in the EUV
spectrometer. A typical spectrum is shown in Fig. S2. The energy axis of our
spectrometer is determined from the spacing of the high harmonics, which is
given by twice the fundamental photon energy of 1.2 eV. This leads to a
relative uncertainty of $<2\%$ on the photon energy calibration. From the
energy-resolved dynamics, we estimate the spectral resolution to be better
than 0.2 eV.

For the determination of the off-diagonal dielectric tensor $\epsilon_{xy}$
from T-MOKE data, the asymmetry was evaluated in 0.1 eV energy windows
separated by 0.3 eV (center-to-center) at energies close to the high harmonic
maxima. Fit results of the static magnetic asymmetries for the extraction of
$\epsilon_{xy}$ (Section III A) together with the observed T-MOKE asymmetry
are shown in Fig. S3 and yield good agreement with the measured static T-MOKE
asymmetries. We note that the T-MOKE asymmetry is strongly reduced in-between
high harmonic energies due to the comparably higher background contribution at
those energies.

Figure S3:  Fit of the static magnetic asymmetries for the extraction of
$\epsilon_{xy}$ as described in Section III A. The results from the fit
procedure (colored circles) provide a satisfactory description of the
experimental data (solid lines).

The transient evolution of the off-diagonal dielectric tensor $\epsilon_{xy}$
was determined from the measured reflectivities $R_{\uparrow/\downarrow}$
(Section III B). For the fitting of $R_{\uparrow/\downarrow}$, good agreement
with the experimental data on early timescales can only be achieved by the
inclusion of transient optical changes of the complex refractive index
$n=1-\delta+i\beta$. In particular, this is important below the resonance
(around $\approx 64$ eV), where we probe states below $E_{\textsubscript{F}}$,
which are most strongly affected by the excitation of electrons by the pump
pulse. Not including the refractive index changes yields a poor agreement
between the measured $R_{\uparrow/\downarrow}$ and the fit, as shown in Fig.
S4. The extracted transient evolution of the real and imaginary part of the
off-diagonal dielectric tensor element $\epsilon_{xy}$ and the optical changes
of $\delta$ and $\beta$ for selected energies around the Ni resonance are
shown in Fig. S5.

Figure S4: Time-resolved analysis of the dielectric tensor, if transient
changes of the refractive index in the sample are neglected. The panels show
the measured (points) and reconstructed (line) transient relative reflectivity
$\Delta R_{\uparrow/\downarrow}(t)$ for opposite magnetization directions (cf.
Eq. 8 in the main text) during optically-induced demagnetization for photon
energies just below (a) and close to (b) the Ni M-edge - equivalent to Fig. 6a
and b in the main text. The exclusion of transient optical changes of the
refractive index results in a poor fit of the experimental data, especially at
the energy below the resonance, where the $\Delta R_{\uparrow/\downarrow}(t)$
curves deviate from the usual mirror-symmetric behavior. At this energy, the
excitation of electrons by the laser pulse is most dominant and has a strong
effect on the refractive index.

##  IX Time-dependent Density Functional Theory

For the TDDFT calculations a pump pulse with a central photon energy of 1.2
eV, a Gaussian intensity profile with FWHM = 47 fs and an incident fluence of
$\approx$ 18 $\nicefrac{{\text{mJ}}}{{\text{cm}^{2}}}$ was used. For the
details of the method and the code see Refs. [35, 55, 50].

Figure S5: Fit results of the transient behavior of $\epsilon_{xy}$ and $n$
for different energies around the Ni M-edge.


11institutetext:  Alexandru Ioan Cuza University Iaşi, Romania
11email: {motroival<EMAIL_ADDRESS>
# A Note on the Performance of Algorithms for Solving Linear Diophantine
Equations in the Naturals

Valeriu Motroi 11 Ştefan Ciobâcă 22

###### Abstract

We implement four algorithms for solving linear Diophantine equations in the
naturals: a lexicographic enumeration algorithm, a completion procedure, a
graph-based algorithm, and the Slopes algorithm. As already known, the
lexicographic enumeration algorithm and the completion procedure are slower
than the other two algorithms. We compare in more detail the graph-based
algorithm and the Slopes algorithm. In contrast to previous comparisons, our
work suggests that they are equally fast on small inputs, but the graph-based
algorithm gets much faster as the input grows. We conclude that
implementations of AC-unification algorithms should use the graph-based
algorithm for maximum efficiency.

##  0.1 Introduction

Solving linear Diophantine equations in the naturals is at the core of AC-
unification algorithms. AC-unification reduces to top-most unification
problems of the form

$f^{*}(u_{1},\ldots,u_{l})=f^{*}(v_{1},\ldots,v_{k}),$

where $u_{1},\ldots,u_{l},v_{1},\ldots,v_{k}$ are variables (possibly with
repetitions) and $f^{*}$ is a variadic symbol corresponding to some AC-symbol
$f$. Solving such a top-most AC-unification problem reduces to solving the
Diophantine equation

$a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}=b_{1}x_{1}+b_{2}x_{2}+\cdots+b_{n}x_{n},$
(1)

where $x_{i}$ ($1\leq i\leq n$) are the unknowns (taking values in the set of
naturals) and $a_{i},b_{j}$ ($1\leq i\leq l$, $1\leq j\leq k$) are the
multiplicities of the corresponding variable among $u_{1},\ldots,u_{l}$ and
$v_{1},\ldots,v_{k}$, respectively. For more details, see the survey of Baader
and Snyder on unification [2].

Therefore, algorithms for computing AC-unifiers make intensive use of a linear
Diophantine equation (LDE) solver. We compare four algorithms for LDE solving.
Our results suggest that the graph-based algorithm is the fastest on modern
computers, in contrast to previous benchmarks, which are older. We conclude
that implementations of AC-unification should consider switching to the graph-
based algorithm.

##  0.2 Algorithms

In this section we briefly describe the known algorithms for solving Equation
1.

###  0.2.1 The Lexicographic Enumeration Algorithm

In this subsection we describe the simplest way of solving Equation 1. We
notice that a linear Diophantine equation with natural solutions can have an
infinite number of solutions. We generally do not need all of them, but just
need a complete set of minimal solutions. A solution
$S_{1}=(x_{1},x_{2},\ldots,x_{n})$ is not minimal if there exists another
solution $S_{2}=(x^{\prime}_{1},x^{\prime}_{2},\ldots,x^{\prime}_{n})$ such
that for all $i$, $S_{1,i}\geq S_{2,i}$ and $S_{1}\neq S_{2}$. The set of
minimal solutions forms a basis. The lexicographic algorithm [7]
lexicographically enumerates all solutions and saves only the minimal ones.
However, we can not enumerate infinitely many solutions; we should have a
bound for $x_{a,i}$ and $x_{b,i}$, where the vectors $x_{a}$ and $x_{b}$ form
a solution of Equation 1. Huet [7] points out that, for a minimal solution,
the unknowns $x_{a,i}$ should be not greater than $\max(b)$ and the unknowns
$x_{b,i}$ should not be greater than $\max(a)$, where $a$ and $b$ are the
coefficients in Equation 1. Lambert [8] gives the stronger bounds
$\sum_{i}x_{a,i}\leq\max(b)$ and $\sum_{i}x_{b,i}\leq\max(a)$. Moreover, we do
not need to enumerate the possible values of all $N$ unknowns, it is enough to
enumerate $N-1$; the last unknown can be found by solving a simple equation.
We can develop this idea further. What happens if we enumerate $N-2$
variables? We get an equation of form $ax+by=c$ and we can solve it using the
extended Euclidian algorithm. With two types of bounds and two types of
_optimizations_ we get 4 similar algorithms that solve Equation 1. The slowest
part of this algorithm is checking if a new solution is minimal or not,
because checking minimality requires comparing the new solution with the other
already generated minimal solutions. For implementation simplicity we rewrite
Equation 1 as:

$a_{1}x_{1}+a_{2}x_{2}+\ldots+a_{n}x_{n}-b_{1}x_{1}-b_{2}x_{2}-\ldots-
b_{n}x_{n}=0$ (2)

If we let $w_{i}=a_{i}-b_{i}$ then Equation 2 can be written as:

$w_{1}x_{1}+w_{2}x_{2}+\ldots+w_{n}x_{n}=0$ (3)

We work with Equation 3, because it is closer to the implementation. In Figure
1 we provide a very generic implementation for the lexicographic algorithm.
The algorithm implements a standard backtracking procedure, with the parameter
$p$ denoting the current unknown. The test $p$ is last allows to implement the
optimizations described above (stop the enumeration at $n-1$ unknowns or at
$n-2$ unknowns).

1 Function  _LexAlg(_p_)_:

2 if  _p is last_ then

3 sol := Solve the remaining equation without enumeration

4

5 if  _sol is Minimal_ then

6 addSolution(sol)

7

8

9 else

10 for (  _$i=0;\ i <bound;\ i=i+1$_ )

11 set sol[p] = i

12

13 LexAlg(p + 1)

14

15

16

17 end if

18

19

Figure 1: The Lexicographic Enumeration Algorithm (generic version).

###  0.2.2 The Completion Procedure

Another way to solve Equation 1 is to compute all minimal solutions by a
_completion procedure_. Such an algorithm is due to Fortenbacher [5], with an
optimization by Guckenbiehl and Herold [6]. For some
$x=(x_{1},x_{2},\ldots,x_{n})$, we denote by $d(x)$ the result of the
expression $d(x)=w_{1}x_{1}+w_{2}x_{2}+\ldots+w_{n}x_{n}$, which we call the
defect of Equation 3. A _proposal_ $p=(x_{1},x_{2},\cdots,x_{n})$ is
characterized by $-\max b\leq d(p)\leq\max a$. A solution is a proposal $p$
that has $d(p)=0$. The algorithm starts with a set of proposals. At each
_completion step_ , it updates every proposal $p$ in the following way:
$\bullet$ if its defect is less than zero, then it increments $x_{i}$ by $1$
for some index $i$ with $w_{i}>0$; $\bullet$ otherwise (if its defect is
positive) it increments $x_{i}$ by $1$ for some $i$ with $w_{i}<0$. If the
result has defect zero then a _minimal solution_ was found. If a proposal is
not minimal then it is discarded, because we can not obtain a _minimal
solution_ from a _non-minimal proposal_. In such a way only minimal solutions
are computed and this is an advantage over _Lexicographic Algorithm_. However,
a solution may be computed several times and we still have to test proposals
for minimality. Guckenbiehl and Herold [6] describe a way to avoid computation
of the same solution several times. To do that we need to select one unique
computation for each solution. That is done by following one rule: a proposal
with negative (positive) defect must not be incremented at a position $i$
(position $j$) if there exists a $k>i$ with $w_{k}>0$ ($k>j$ with $w_{k}<0$).
We present this version of the completion procedure in Figure 2.

1

2Function  _CompAlg(_w_)_:

3 // init the proposal set

4 pSet = empty set of proposals

5 for (  _$i=0;\ i <n;\ i=i+1$_ )

6 p = new proposal

7 p[i] = 1

8 pSet.add(p)

9

10

11

12 while  _pSet is not empty_ do

13 // completion step

14 pSetNew = a new proposal set

15 for (  _$p\ in\ pSet$_ )

16 for (  _$i=n-1;\ i\geq 0;\ i=i-1$_ )

17 if  _$(d(p) <0\ and\ w_{i}<0)\ or\ (d(p)>0\ and\ w_{i}>0)$_ then

18 continue

19

20 auxProposal = copyOf(p)

21 auxProposal[i] = auxProposal[i] + 1

22 if  _auxProposal has defect zero_ then

23 addSolution(auxProposal)

24

25 else

26 if  _auxProposal is minimal_ then

27 pSetNew.add(auxProposal)

28

29

30 end if

31 // avoiding multiple computations of the same solution

32 if  _$p[i] >0$_ then

33 break

34

35

36

37

38

39 pSet = pSetNew

40

41 end while

42

43

44

Figure 2: The Completion Procedure described by Fortenbacher [5], with an
optimization by Guckenbiehl and Herold [6].

###  0.2.3 The Graph Algorithm

Clausen and Fortenbacher [3] described a further optimization of the
completion procedure. We call the resulting algorithm the _Graph Algorithm_.
In order to avoid all additions and subtractions, they represent Equation 3 as
a graph. The graph representation of a linear Diophantine equation is a
labelled digraph with the set $\\{d\in\mathbb{Z}|-\max b\leq d\leq\max a\\}$
representing the nodes and set $\\{d\rightarrow_{w_{i}}d+w_{i}|i\leq n\\}$
representing labelled edges. In other words, the nodes are the defect of any
proposal and an edge $d\rightarrow_{w_{i}}d+w_{i}$ corresponds to incrementing
a proposal at position $i$. A solution in this graph is a walk that begins in
zero and ends in zero. An advantage over the _completion procedure_ is that
the minimality check of a solution is also transformed into a graph problem.
In this graph, a walk that corresponds to the solution
$s=(s_{1},s_{2},\ldots,s_{n})$ is non-minimal if there is another walk
$z=(z_{1},z_{2},\ldots,z_{n})$ that is shorter than $s$ and also is bounded by
$s$, in other words $z_{i}\leq s_{i}$ for all $i$. A detailed implementation
of this algorithm written in Pascal is provided by Clausen and Fortenbacher
[3].

###  0.2.4 The Slopes Algorithm

The Slopes Algorithm described by Filgueiras and Tomás [4] is an optimization
of the lexicographic algorithm. The enumeration is performed _for all but
three_ of the unknowns and an equation of the following form:

$ax=by+cz+v,\ a,b,c,x,y,z\in\mathbb{N},\ v\in\mathbb{Z}$ (4)

is solved. Filgueiras and Tomás [4] describe a way of finding directly all
minimal solutions for Equation 4. The idea is that, if minimal solutions of
Equation 4 are ordered with $z$ strictly increasing, then both the solution
with the smallest $z$ and the difference between consecutive solutions can be
computed algebraically. Geometrically, this can be seen as a Pareto frontier
of all solutions projected onto the _YZ-plane_ if $v\geq 0$ and is a polygonal
line when $v<0$. We can project solutions to 2D space because it is well known
that each solution of Equation 4 verifies the congruence:

$by+cz\equiv-v\ \ \ (mod\ a).$ (5)

And reciprocally, that each solution of Equation 5 corresponds to some
integral solution of Equation 4. In Figure 3 we present the implementation of
Slopes algorithm for solving $ax+by+cz=0$.

1 Function  _Slopes(_a, b, c_)_:

2 gb=gcd(a,b); gc=gdc(a,c); G=gcd(gb,c)

3 ymax=a/gb; zmax=a/gc

4 dz=gb/G; dy=(c*multiplier(b,a)/G) mod ymax

5 y=ymax-dy; z=dz

6 Solutions={(b/gb, ymax, 0), (c/gc, 0, zmax), ((b*y+c*z)/a, y, z)}

7 while  _dy $>$ 0_ do

8 while  _y $>$ dy_ do

9 y=y-dy; z=z+dz

10 Solutions.add(((b*y)+c*z)/a,y,z))

11

12 end while

13 f=dy/y; dy=dy mod y; dz=f*z+dz

14

15 end while

16 return Solutions

17

18

// multiplier(a, b) is an integer $m_{b}$ such that $gcd(a,b)=m_{a}*a+m_{b}*b$

Figure 3: The Slopes algorithm of Filgueiras and Tomás for the equation
$ax=by+cz$.

##  0.3 Methodology

We have implemented all algorithms in C++. The first two algorithms are
clearly slower than the last two. Therefore, we made a more detailed
comparison between the Graph and Slopes algorithms, reproducing the comparison
by Filgueiras and Tomás [4]. As our implementation of the Slopes algorithm is
somewhat slower than the well known and optimized C implementation [1], we use
the later for the comparison. All of our code, including instructions for
reproducing our results (Figures 1-4), are available at
https://github.com/Djok216/LDEAlgsComparison.

To measure the running time we use the python _subprocess_ and _time_
libraries. The first one is used for spawning the executables of the
algorithms and the later for measuring running time using _perf_counter_. We
set a timeout of $10$ minutes for the spawned processes. The tests are
generated using _random.randint_ and the left side is sorted in decreasing
order and the right side in increasing order, because in most cases this
ordering speeds up the Slopes algorithm as explained by Filgueiras and Tomás
[4].

The tests are divided in $160$ classes determined by $N\in\\{1,2,3,4\\}$ \-
the number of unknowns on the left hand side, $M\in\\{2,3,4,5,6,7,8,9\\}$ \-
the number of unknowns on the right hand side such that $N\leq M$ and
$\emph{MaxValue}\in\\{2,3,5,13,29,39,107,503,1021\\}$\- the maximum
coefficient of any unknown. We manually set _MaxValue_ as part of the
coefficients on the right hand side, because there are always more unknowns on
the right hand side than left hand side ($N\leq M$). Every class contains $10$
different tests generated randomly. We use a fixed seed for reproducibility
purposes.

We calculate the running time after running the same test with the same
algorithm $5$ times. The running time for that algorithm on that specific test
is considered to be the arithmetic mean of $3$ out of $5$ remaining values
after removing the smallest and the biggest value. The exception is when an
algorithm runs for more than $15$ seconds. In this case we stop running the
same test and calculate the arithmetic mean of running times available at the
moment. For example, if an algorithm runs two times in $14.9$ seconds and the
third time in $15.2$, then we stop running this test after third run and the
time is considered to be $(2*14.9+15.2)/3=15$ seconds. We also set a timeout
of $10$ minutes, after which we automatically stop the algorithm.

For every test in a given class, we add $1$ point to the algorithm taking the
least time and $0$ points to the other. In case of a tie, we add $0.5$ to both
algorithms. Therefore, a score of $6:4$ would mean that the first algorithm
performed better $6$ times, while the second algorithm $4$ times out of the
$10$ tests for a given class.

We consider an algorithm to win a particular class if it scores at least $8$
points. The definition of a win is justified statistically by Filgueiras and
Tomás [4].

For compiling the code we use _GCC 5.4_. Below are the commands used to
compile the programs:

    gcc -static slopesV7i.c -std=c11 -O3 -o slopesV7i
    g++ -static -lm -s -x c++ -std=c++17 -O3 -o graph graph.cpp

We run the benchmark on an Intel Xeon machine with two processors and 24
hardware threads (12 physical cores) with a clock speed of 2.67 GHz.

We repeat the measurements made by Filgueiras and Tomás [4], but we also
compare the two algorithms using an epsilon of $0.01$. By this we mean that
the algorithms are considered equally fast if their running times differ by a
value smaller than $0.01$ seconds. Moreover, we also compute the overall time
spent in every class of tests.

##  0.4 Discussion

Figure 4 contains a summary of the results. The Slopes algorithm wins $103$
classes out of $160$ and Graph algorithm wins $7$ classes. Filgueiras and
Tomás [4] find that Slopes wins $88$ classes and Graph wins $33$ classes.
These results suggest that the Slopes algorithm is faster than the Graph
algorithm.

We redo the same comparison, but this time we consider the two algorithms to
be equal if their running time differs by at most $\epsilon=0.01$ seconds. The
results are summarized in Figure 5. Each algorithm now has $6$ wins and for
most of the classes there is a tie. This means that the algorithms are quasi-
equal in efficiency.

Going further, we analyze the _total time_ spent in each test class by each
algorithm. The results are summarized in Figure 7. We see that in classes
where the Slopes algorithm wins, the difference is very small. However, in the
classes in which the Graph algorithm wins, the difference is huge. The total
time spent in all $160$ classes for the Slopes algorithm is $4284.81$ seconds
and $724$ seconds for the Graph algorithm. The counts ($4284.81$ seconds,
$724$ seconds) should be interpreted taking into account that they contain $1$
timeout of $10$ minutes for Graph and $4$ timeouts of $10$ minutes for Slopes,
as summarized in Figure 6.

Based on our results, we conclude that the Graph algorithm is significantly
faster than Slopes for bigger instances and roughly as fast for small
instances.

_Practical relevance of our benchmark._ In most cases, the bottleneck in
AC(U)-unification algorithms is combining the solutions to the linear
Diophantine equations themselves. However, there are AC(U)-unification
problems where solving Equation 1 is the slow part. An example is an ACU-
unification problem with a single AC-function $f$ and 8 different variables,
which can be constructed based on Equation 6:

$104x_{1}+167x_{2}=165x_{3}+154x_{4}+148x_{5}+159x_{6}+174x_{7}+150x_{8}.$ (6)

The ACU-unification problem is the following:

$f_{104}(u_{1})+f_{167}(u_{2})=_{?}f_{165}(u_{3})+f_{154}(u_{4})+f_{148}(u_{5})+f_{159}(u_{6})+f_{174}(u_{7})+f_{150}(u_{8}),$
(7)

where $f_{k}(v)=f(v,v,\ldots,v)$ (such that $v$ has $k$ occurrences).

Equation 6 has a basis of size $5510$. Finding the basis is significantly
slower than combining its solutions and creating the ACU-unifier. On the same
hardware as described in Section 0.3, the Graph algorithm takes about $0.6$
seconds to solve the linear Diophantine equation above, while combining the
solutions into an ACU-unifier takes $0.15$ seconds. To compute the ACU-
unifier, we use the algorithm presented by Baader and Snyder in their survey
on unification [2]. Therefore, at least on some AC-unification problems,
solving LDEs dominates the running time.

_Conclusion._ Implementations of AC unification should therefore consider
using the Graph algorithm, or choosing between Graph and Slopes, depending on
problem size.

## References

  * [1] Slopes webpage.  https://www.dcc.fc.up.pt/dioph.  Last accessed: 2020; The site is currently down.
  * [2] Franz Baader, Wayne Snyder, Paliath Narendran, Manfred Schmidt-Schauß, and Klaus U. Schulz.  Unification theory.  In John Alan Robinson and Andrei Voronkov, editors, Handbook of Automated Reasoning (in 2 volumes), pages 445–532. Elsevier and MIT Press, 2001.
  * [3] Michael Clausen and Albrecht Fortenbacher.  Efficient solution of linear diophantine equations.  Journal of Symbolic Computation, 8(1-2):201–216, 1989.
  * [4] Miguel Filgueiras and Ana Paula Tomas.  A fast method for finding the basis of non-negative solutions to a linear diophantine equation.  Journal of Symbolic Computation, 19(6):507–526, 1995.
  * [5] A Fortenbacher.  Algebraische uni kation.  PhD thesis, Diplomarbeit, Institut fr Informatik, Universit t Karlsruhe, 1983.
  * [6] Thomas Guckenbiehl and Alexander Herold.  Solving linear diophantine equations.  Fachbereich Informatik, Universität Kaiserslautern, 1985.
  * [7] Gerald Huet.  An algorithm to generate the basis of solutions to homogeneous linear diophantine equations.  Information Processing Letters, 7(3):144 – 147, 1978.
  * [8] Jean-Luc Lambert.  Une borne pour les générateurs des solutions entières positives d’une équation diophantienne linéaire.  Université Paris-Sud, Laboratoire de Recherche en Informatique, 1987\.

| A | 2 | 3 | 5 | 13 | 29 | 39 | 107 | 503 | 1021
---|---|---|---|---|---|---|---|---|---|---
N | M |  |  |  |  |  |  |  |  |
1 | 2 | 2:8 | 2:8 | 2:8 | 5:5 | 2:8 | 4:6 | 4:6 | 1:9 | 0:10
1 | 3 | 2:8 | 2:8 | 3:7 | 2:8 | 1:9 | 3:7 | 1:9 | 0:10 | 0:10
1 | 4 | 3:7 | 3:7 | 2:8 | 2:8 | 1:9 | 0:10 | 0:10 | 0:10 | 0:10
1 | 5 | 4:6 | 2:8 | 2:8 | 2:8 | 0:10 | 3:7 | 1:9 | 0:10 | 0:10
1 | 6 | 3:7 | 3:7 | 2:8 | 1:9 | 0:10 | 1:9 | 0:10 | 0:10 |
1 | 7 | 4:6 | 4:6 | 3:7 | 2:8 | 1:9 | 0:10 | 0:10 | 0:10 |
1 | 8 | 1:9 | 2:8 | 3:7 | 0:10 | 0:10 | 0:10 | 0:10 |  |
1 | 9 | 4:6 | 2:8 | 1:9 | 1:9 | 2:8 | 1:9 |  |  |
2 | 2 | 3:7 | 1:9 | 1:9 | 2:8 | 1:9 | 0:10 | 1:9 | 0:10 | 0:10
2 | 3 | 3:7 | 2:8 | 2:8 | 1:9 | 0:10 | 2:8 | 4:6 | 10:0 | 7:3
2 | 4 | 2:8 | 3:7 | 3:7 | 0:10 | 1:9 | 3:7 | 6:4 | 9:1 | 9:1
2 | 5 | 5:5 | 5:5 | 3:7 | 3:7 | 3:7 | 6:4 | 9:1 | 9:1 |
2 | 6 | 2:8 | 2:8 | 0:10 | 0:10 | 2:8 | 5:5 | 6:4 |  |
2 | 7 | 4:6 | 1:9 | 3:7 | 0:10 | 1:9 | 6:4 |  |  |
2 | 8 | 4:6 | 4:6 | 1:9 | 2:8 | 4:6 | 9:1 |  |  |
3 | 3 | 2:8 | 0:10 | 2:8 | 0:10 | 0:10 | 2:8 | 2:8 | 7:3 |
3 | 4 | 2:8 | 3:7 | 3:7 | 2:8 | 0:10 | 2:8 | 4:6 |  |
3 | 5 | 4:6 | 2:8 | 2:8 | 1:9 | 2:8 | 5:5 | 9:1 |  |
3 | 6 | 2:8 | 2:8 | 1:9 | 0:10 | 3:7 | 4:6 |  |  |
4 | 4 | 4:6 | 2:8 | 1:9 | 0:10 | 2:8 | 0:10 | 5:5 |  |
4 | 5 | 3:7 | 2:8 | 1:9 | 0:10 | 2:8 | 5:5 |  |  |
Figure 4:  Comparison of Graph and Slopes algorithms. For each of the $160$ test classes characterized by $N,M$ and $A$ (MaxValue), we count the number of times Graph is faster versus the number of times Slopes is faster out of $10$ tests for each class. | A | 2 | 3 | 5 | 13 | 29 | 39 | 107 | 503 | 1021
---|---|---|---|---|---|---|---|---|---|---
N | M |  |  |  |  |  |  |  |  |
1 | 2 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5
1 | 3 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5 | 4:5
1 | 4 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 2:7 | 1:9
1 | 5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5 | 0:9 | 0:10
1 | 6 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 2:7 | 1:9 |
1 | 7 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5 | 2:7 | 0:9 |
1 | 8 | 5:5 | 5:5 | 5:5 | 5:5 | 4:6 | 4:5 | 2:8 |  |
1 | 9 | 5:5 | 5:5 | 5:5 | 5:5 | 4:6 | 3:7 |  |  |
2 | 2 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5 | 3:6
2 | 3 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 9:0 | 6:3
2 | 4 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 7:3 | 9:1 | 9:1
2 | 5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:4 | 9:1 | 9:1 |
2 | 6 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 6:3 |  |
2 | 7 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 |  |  |
2 | 8 | 5:5 | 5:5 | 5:5 | 5:5 | 6:4 | 6:3 |  |  |
3 | 3 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 4:5 | 7:3 |
3 | 4 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 3:6 |  |
3 | 5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:4 | 9:0 |  |
3 | 6 | 5:5 | 5:5 | 5:5 | 5:5 | 5:4 | 4:5 |  |  |
4 | 4 | 5:5 | 5:5 | 5:5 | 5:5 | 5:4 | 4:6 | 5:5 |  |
4 | 5 | 5:5 | 5:5 | 5:5 | 5:5 | 5:5 | 6:3 |  |  |
Figure 5:  Comparison of the Graph and Slopes algorithms. Same as the previous figure, but the algorithms are considered tied on tests on which their running times differ by at most $0.01$ seconds. | A | 2 | 3 | 5 | 13 | 29 | 39 | 107 | 503 | 1021
---|---|---|---|---|---|---|---|---|---|---
N | M |  |  |  |  |  |  |  |  |
1 | 2 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
1 | 3 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
1 | 4 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
1 | 5 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
1 | 6 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |
1 | 7 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |
1 | 8 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |
1 | 9 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |  |
2 | 2 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
2 | 3 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0
2 | 4 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 1:0 | 0:0
2 | 5 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:4 |
2 | 6 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |
2 | 7 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |  |
2 | 8 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |  |
3 | 3 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |
3 | 4 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |
3 | 5 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |
3 | 6 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |  |
4 | 4 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |
4 | 5 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 | 0:0 |  |  |
Figure 6: Number of timeouts ($10$ minutes) for the Graph and Slopes algorithms on each class. | A | 13 | 29 | 39 | 107 | 503 | 1021
---|---|---|---|---|---|---|---
N | M |  |  |  |  |  |
1 | 2 | .0:.0 | .0:.0 | .0:.0 | .0:.0 | .0:.0 | .1:.0
1 | 3 | .0:.0 | .0:.0 | .0:.0 | .0:.0 | .1:.0 | .1:.0
1 | 4 | .0:.0 | .0:.0 | .0:.0 | .0:.0 | .2:.0 | .8:.0
1 | 5 | .0:.0 | .0:.0 | .0:.0 | .1:.0 | 2.7:.1 | 5.7:.2
1 | 6 | .0:.0 | .0:.0 | .0:.0 | .1:.0 | 9.8:.3 |
1 | 7 | .0:.0 | .0:.0 | .1:.0 | .4:.1 | 20.5:.4 |
1 | 8 | .0:.0 | .1:.1 | .1:.0 | 1.8:.5 |  |
1 | 9 | .0:.0 | .1:.1 | .2:.0 |  |  |
2 | 2 | .0:.0 | .0:.0 | .0:.0 | .0:.0 | .1:.0 | .4:.1
2 | 3 | .0:.0 | .0:.0 | .0:.0 | .1:.1 | .2:.5 | 2.9:3.0
2 | 4 | .0:.0 | .0:.0 | .1:.0 | .2:.3 | 602.1:190.0 | 16.8:550.0
2 | 5 | .0:.0 | .0:.0 | .1:.1 | .2:.7 | 25.2:3333.7 |
2 | 6 | .1:.0 | .2:.2 | .1:.2 | 1.1:12.0 |  |
2 | 7 | .0:.0 | .1:.1 | .1:.1 |  |  |
2 | 8 | .1:.0 | .2:.4 | .4:1.1 |  |  |
3 | 3 | .0:.0 | .1:.0 | .1:.0 | .1:.1 | 17.0:68.5 |
3 | 4 | .0:.0 | .1:.0 | .1:.1 | .8:1.7 |  |
3 | 5 | .0:.0 | .1:.1 | .1:.1 | 3.3:28.2 |  |
3 | 6 | .1:.0 | .1:.1 | .4:.6 |  |  |
4 | 4 | .1:.0 | .1:.1 | .2:.2 | 3.3:85.8 |  |
4 | 5 | .1:.0 | .2:.2 | .4:.6 |  |  |
Figure 7:  The total time, expressed in seconds, spent by each algorithm
(Graph and Slopes) on all tests for each class. Columns with A $<13$ are
excluded because the values are very close to zero.