groups | ||
.gitignore | ||
AutFn.jl | ||
CPUselect.jl | ||
FPgroup.jl | ||
FPGroups_GAP.jl | ||
LICENSE.md | ||
main.jl | ||
README.md | ||
SLn.jl |
This repository contains code for computations in Certifying Numerical Estimates of Spectral Gaps.
Installing
To run the code You need julia-v0.5
(should work on v0.6
, but with warnings).
You also need to install julia packages: Nemo-v0.6.3
, ArgParse
. To do so in julia
's REPL run:
Pkg.update()
Pkg.add("Nemo")
Pkg.add("ArgParse")
Then clone the main repository of Groups.jl
, GroupRings.jl
and PropertyT.jl
:
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/Groups.jl.git")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/GroupRings.jl.git")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/PropertyT.jl.git")
Pkg.resolve()
This should resolve all dependencies (e.g. install JuMP
, SCS
, IntervalArithmetic
, JLD
, Memento
). Exit julia and finally clone this repository:
git clone https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT.git
cd GroupswithPropertyT
Running
Naive implementation
To check that \Delta^2-\lambda\Delta
is not decomposable to a sum of hermitian squares of elements in the ball of radius 2
in SL(2,7)
run
julia SL.jl -N 2 -p 7 --radius 2 --iterations 100000
(~30 seconds, depending on hardware). The monotonous decreasing \lambda
during the optimisation is in column pri obj
(or dua obj
) of solver.log
.
Compare this to
julia SL.jl -N 2 -p 7 --radius 3 --iterations 100000
which finds \lambda \geq 0.5857
and decomposes \Delta^2-\lambda\Delta
into sum of 47
hermitian squares in less than 20 seconds (including certification).
If You see in the output (or in full.log
) that the upper end of the interval where \lVert\Delta^2 - \lambda\Delta - \sum{\xi_i}^*\xi_i\rVert_1
belongs to is too large (resulting in positive Floating point distance
, but negative The Augmentation-projected actual distance
), decrease the --tol
parameter, e.g.
julia SL.jl -N 2 -p 7 --radius 3 --iterations 100000 --tol 1e-9
to achieve a better estimate (the residuals $\ell_1$-norm should be around \|B_d(e))\|\cdot tol
)
Symmetrization enhanced implementation
A newer version of the software uses orbit and Wedderburn decomposition to effecitively find a (much) smaller optimisation problem to compute the spectral gap \lambda
. In particular the solution to the original (naive) optimisation problem can be reconstructed from the solution of the symmetrised one.
E.g. Run
julia SL_orbit.jl -N 4 --radius 2 --upper-bound 1.3
to find (and certify) the spectral gap for SL(4, \mathbb{Z})
is at least 1.2999...
in just under 2
minutes time (for comparison this result requires over 5
hours in the old implementation on the same hardware).
To replicate the results of \operatorname{Aut}(\textbf{F}_5)
has property (T) You neet to run (on a 4
-core CPU)
julia ../AutFN_orbit.jl -N 5 --upper-bound 1.2 --iterations 24000000 --cpus 4
Note that this computation took more than 12
days and required at least 32
GB of ram (and possible more).
Help
julia SL.jl --help
usage: SL.jl [--tol TOL] [--iterations ITERATIONS]
[--upper-bound UPPER-BOUND] [--cpus CPUS] [-N N] [-p P]
[--radius RADIUS] [-h]
optional arguments:
--tol TOL set numerical tolerance for the SDP solver
(type: Float64, default: 1.0e-6)
--iterations ITERATIONS
set maximal number of iterations for the SDP
solver (default: 20000) (type: Int64, default:
50000)
--upper-bound UPPER-BOUND
Set an upper bound for the spectral gap (type:
Float64, default: Inf)
--cpus CPUS Set number of cpus used by solver (type:
Int64)
-N N Consider elementary matrices EL(N) (type:
Int64, default: 2)
-p P Matrices over field of p-elements (p=0 => over
ZZ) (type: Int64, default: 0)
--radius RADIUS Radius of ball B_r(e,S) to find solution over
(type: Int64, default: 2)
-h, --help show this help message and exit
Specific version of 1703.09680
To checkout the specific versions of packages used for Certifying Numerical Estimates of Spectral Gaps run (inside the cloned GroupswithPropertyT
)
git checkout 1703.09680v1
Unfortunately: You need to link ~/.julia/v0.5/GroupRings
to ~/.julia/v0.5/GroupAlgebras
due to change in the name of the package. Then run in julia
Pkg.checkout("GroupRings", "1703.09680v1")
Pkg.checkout("PropertyT", "1703.09680v1")
Pkg.resolve()
Specific version of 1712.07167
You need to run julia-0.6
.
Clone https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT
and checkout the 1712.07167
branch:
git clone https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT.git
cd ./GroupsWithPropertyT
git checkout 1712.07167
In julia
s REPL execute
Pkg.add("ArgParse")
Pkg.add("Nemo")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/Groups.jl.git")
Pkg.checkout("Groups", "1712.07167")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/GroupRings.jl.git")
Pkg.checkout("GroupRings", "1712.07167")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/PropertyT.jl.git")
Pkg.checkout("PropertyT", "1712.07167")
Pkg.checkout("SCS")
Pkg.build("SCS")
This should resolve all the dependencies. Quit julia
and place the oSAutF5_r2
folder downloaded from here inside GroupsWithPropertyT
folder. To verify the decomposition of \Delta^2 - \lambda \Delta
for the group run (if You have a 4
-core CPU at Your disposal)
julia AutFN_orbit.jl -N 5 --upper-bound=1.2 --cpus 4
If You want to generate pm
and other files on Your own delete everything from the oSAutF5_r2
folder but 1.2
folder and its contents and run the same command again.
Note: You need at least 32
GB of RAM and spare 24
h of Your CPU.