-
Notifications
You must be signed in to change notification settings - Fork 93
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
The Faure sequence is wrong #2653
Comments
@mbaudin47 Nice catch, and thanks for the detailed analysis. The faulty part seems to be in Once the bug is fixed, using your script I get (after replacing im.distributionX by distribution):
|
I try to improve some of the low discrepancy unit tests in #2654. I was not able to reproduce the bug based on my Linux-build of the lib: do you know why? |
Is there a workaround, like uninstalling PrimeSieve? |
no need to uninstall, you can pass -DUSE_PRIMESIEVE=OFF to cmake |
What if the installation is based on Conda: is there a way to remove that package/module, or is this integrated within the OT binary? |
its not possible to change it at runtime |
@regislebrun I found the issue. Here are the first 4 points of the Faure sequence in the current's master:
This is wrong. The 3d point is in base 8, not in base 4 as expected. The reason behind this is because we removed the first point, the infamous import openturns as ot
import openturns.viewer as viewer
import matplotlib.pyplot as plt
basis = 2
dimension = 2
sample_size = basis**dimension
distribution = ot.ComposedDistribution([ot.Uniform(0.0, 1.0)] * dimension)
sequence = ot.FaureSequence()
experiment_QMC = ot.LowDiscrepancyExperiment(sequence, distribution, sample_size, False)
sample = experiment_QMC.generate()
fig = viewer.PlotDesign(
sample,
subdivisions=[basis] * dimension,
bounds=ot.Interval([0.0] * dimension, [1.0] * dimension),
)
plt.title(f"n = {sample_size}")
plt.xlim(-0.1, 1.1)
plt.ylim(-0.1, 1.1)
fig.set_figwidth(3.0)
fig.set_figheight(3.0) this produces: Figure 1. The faulty Faure sequence in OpenTURNS 1.23. The correct 4 points are :
This produces: Figure 2. The correct Faure sequence. A. Owen explained this in 1. A significant contribution of this paper is that Owen presents examples where removing the first point in the sequence reduces the convergence speed of the method. Please have a look at the figure 2 page 9. In the paper, $\hat{\mu}{x,1}$ is the average of the first $n$ points where the first point was skipped and $\hat{\mu}{x,2}$ is the average of the first One solution is: put the 0 back (which restores the convergence rate) and scramble the sequence by default (which solves the 0 issue). Quoting 1: "With digital nets as with antibiotics, one should take the whole sequence." I will create a new issue on the topic with title: "The zero should be included in some low discrepancy sequences". This issue will impact Sobol', Faure and perhaps other sequences as well. Footnotes
|
What happened?
The Faure sequence generates wrong points in any dimension.
Here are the proofs of this.
Many thanks to Félix Husson (EDF & Institut Galilée) for pointing that bug.
One of the reasons of the bug is undetected is the way the unit test t_FaureSequence_std.cxx is implemented. Since the algorithm produces a set of points, the simplest and most efficient way to implement the unit test is to check the coordinates of the set of points against a pre-defined reference$\pi$ . Unfortunately, the algorithm seems to converge with relative accuracy equal to $10^{-4}$ . Actually, this unit test is still of poor value. Indeed, the fact that the estimate converges is a weak proof that the method is OK. Indeed, we may expect that the rate of convergence is OK (which is not). Finally, the sample size is equal to 1000, instead of being equal to a power of the basis, i.e. 2 in this particular case.
Sample
. This reference sample can be computed from another library, e.g. Matlab, Scilab, Mathematica, etc. Several dimensions e.g. 2, 3, and 4 should be checked. Instead, the first part of the current unit test checks the library against itself, which prevents from detecting any bug. The second part of the unit test estimates the numberHow to reproduce the issue?
Proof #1: In dimension 2
Figure 1. The first 4 points of the Faure sequence in dimension 2. There should be one single point for each elementary volume, but the upper left cell contain 2 points.
Proof #2: In dimension 3
The script below defines the first 9 points of the Faure sequence in dimension 3. This is from 1.
Now compare to the result from OpenTURNS.
which prints:
We see that the basis is equal to 2 instead of 3. We see that the third dimension is a copy of the first one.
Proof #3: Convergence on GSobol'
Notice that the lack of convergence of the faulty Faure sequence is not so obvious on the Ishigami function, because the third input variable is no so influential. Only the speed of convergence is affected here.
We consider the GSobol' test function and compute its mean.
We get:
Version
1.22
Operating System
unknown
Installation media
unknown
Additional Context
No response
Footnotes
"Low Discrepancy Toolbox Manual", Michael Baudin. Version 0.1. May 2013. https://gitlab.com/scilab/forge/lowdisc ↩
The text was updated successfully, but these errors were encountered: