144 lines
6.5 KiB
Markdown
144 lines
6.5 KiB
Markdown
# DEPRECATED!
|
|
|
|
This repository has not been updated for a while!
|
|
If You are interested in replicating results for [1712.07167](https://arxiv.org/abs/1712.07167) please check [these instruction](https://kalmar.faculty.wmi.amu.edu.pl/post/1712.07176/)
|
|
Also [this notebook](https://nbviewer.jupyter.org/gist/kalmarek/03510181bc1e7c98615e86e1ec580b2a) could be of some help. If everything else fails the [zenodo dataset](https://zenodo.org/record/1133440) should contain the last-resort instructions.
|
|
|
|
This repository contains some legacy code for computations in [Certifying Numerical Estimates of Spectral Gaps](https://arxiv.org/abs/1703.09680).
|
|
|
|
# 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:
|
|
```julia
|
|
Pkg.update()
|
|
Pkg.add("Nemo")
|
|
Pkg.add("ArgParse")
|
|
```
|
|
Then clone the main repository of `Groups.jl`, `GroupRings.jl` and `PropertyT.jl`:
|
|
```julia
|
|
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:
|
|
```shell
|
|
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
|
|
```shell
|
|
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
|
|
```shell
|
|
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
|
|
```shell
|
|
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)
|
|
```shell
|
|
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
|
|
|
|
```shell
|
|
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](https://arxiv.org/abs/1703.09680)
|
|
|
|
To checkout the specific versions of packages used for [Certifying Numerical Estimates of Spectral Gaps](https://arxiv.org/abs/1703.09680) run (inside the cloned `GroupswithPropertyT`)
|
|
```shell
|
|
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`
|
|
```julia
|
|
Pkg.checkout("GroupRings", "1703.09680v1")
|
|
Pkg.checkout("PropertyT", "1703.09680v1")
|
|
Pkg.resolve()
|
|
```
|
|
|
|
# Specific version of [1712.07167](https://arxiv.org/abs/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
|
|
```julia
|
|
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](https://cloud.impan.pl/s/fGIpxvxdTYYkUxK) 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
|
|
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.
|