Compare commits
92 Commits
enh/modula
...
master
Author | SHA1 | Date | |
---|---|---|---|
fa326a147f | |||
f1d0ff9c14 | |||
8666cc6b2c | |||
9fc23c43d7 | |||
c075b93313 | |||
bf8fc67bb4 | |||
523d783614 | |||
7b06dc1eb2 | |||
7dd061cdb7 | |||
b45adc2e00 | |||
8ee8eebd9e | |||
4cd2212554 | |||
b84b23d486 | |||
c7b8776e2d | |||
1b45625a71 | |||
1b6793f37c | |||
8a2aa6542e | |||
aaa36b2d5c | |||
88fa1ded31 | |||
b41f2ccdc8 | |||
1ea396330c | |||
a1e4a917a6 | |||
385d2d4f5e | |||
e02b410240 | |||
c8f58e1c93 | |||
0a0856bb51 | |||
df4b63a6a6 | |||
01405cb3cc | |||
6abb2c4186 | |||
0cae4882f1 | |||
707efaca3a | |||
57e9e3c404 | |||
000069961b | |||
ab49755863 | |||
b5b9917536 | |||
95066b9c56 | |||
42f915b91d | |||
1e54e25672 | |||
45d8d85189 | |||
7257c02820 | |||
2c7bd86418 | |||
97f64fdee3 | |||
87658ea46e | |||
3d59ecc874 | |||
16bc76e950 | |||
5ea5093f42 | |||
7f4824492c | |||
02825a8ec0 | |||
34066a7128 | |||
52b0e598c6 | |||
fd29784a00 | |||
1d82aeed8d | |||
7dc95cf93a | |||
788da99d82 | |||
6f0f1d5cc6 | |||
3859a26c22 | |||
b5cf3946a2 | |||
8a2d6086cb | |||
0d2f15c887 | |||
80f181da11 | |||
b23a98d23e | |||
df940c8c07 | |||
6acdff2b70 | |||
ed12d87b7a | |||
e0d3cb607b | |||
10cbd4c6f3 | |||
4c26db6ee8 | |||
98b2417ae1 | |||
a75ee1f645 | |||
2ae11d9f33 | |||
76ff889366 | |||
cb16c78690 | |||
9cc5bcfc00 | |||
961f04b964 | |||
98df554624 | |||
476d532d93 | |||
122ebe92bf | |||
86cadd0440 | |||
403d7f7921 | |||
72f8a9d02c | |||
256422cf1b | |||
6d3872ea8d | |||
a33110937a | |||
6c981817fa | |||
c345d664a7 | |||
9d6a2df02d | |||
3e1ec02c8c | |||
14cfc06b7e | |||
515d8e0e14 | |||
e6efa6085a | |||
5fb72bb8e8 | |||
09eeffcc8b |
16
.gitignore
vendored
16
.gitignore
vendored
@ -1,7 +1,15 @@
|
|||||||
|
Articles
|
||||||
|
Higman
|
||||||
|
MCG*
|
||||||
|
notebooks
|
||||||
|
Oldies
|
||||||
|
oSAutF*
|
||||||
|
oSL*
|
||||||
|
SAutF*
|
||||||
|
SL*_*
|
||||||
*ipynb*
|
*ipynb*
|
||||||
*.gws
|
*.gws
|
||||||
*/*.jld
|
|
||||||
*/*.log
|
|
||||||
Old*
|
|
||||||
.*
|
.*
|
||||||
o*
|
tests*
|
||||||
|
*.py
|
||||||
|
*.pyc
|
||||||
|
118
AutFN.jl
118
AutFN.jl
@ -1,118 +0,0 @@
|
|||||||
using ArgParse
|
|
||||||
|
|
||||||
using Nemo
|
|
||||||
import SCS.SCSSolver
|
|
||||||
using PropertyT
|
|
||||||
|
|
||||||
using Groups
|
|
||||||
Nemo.setpermstyle(:cycles)
|
|
||||||
|
|
||||||
#=
|
|
||||||
Note that the element
|
|
||||||
α(i,j,k) = ϱ(i,j)*ϱ(i,k)*inv(ϱ(i,j))*inv(ϱ(i,k)),
|
|
||||||
which surely belongs to ball of radius 4 in Aut(F₄) becomes trivial under the representation
|
|
||||||
Aut(F₄) → GL₄(ℤ)⋉ℤ⁴ → GL₅(ℂ).
|
|
||||||
Moreover, due to work of Potapchik and Rapinchuk [1] every real representation of Aut(Fₙ) into GLₘ(ℂ) (for m ≤ 2n-2) factors through GLₙ(ℤ)⋉ℤⁿ, so will have the same problem.
|
|
||||||
|
|
||||||
We need a different approach: Here we actually compute in Aut(𝔽₄)
|
|
||||||
=#
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Generating set
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function SOutFN_generating_set(N::Int)
|
|
||||||
|
|
||||||
SOutFN = AutGroup(FreeGroup(N), special=true, outer=true)
|
|
||||||
S = gens(SOutFN);
|
|
||||||
S = [S; [inv(s) for s in S]]
|
|
||||||
|
|
||||||
return SOutFN, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Parsing command line
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function cpuinfo_physicalcores()
|
|
||||||
maxcore = -1
|
|
||||||
for line in eachline("/proc/cpuinfo")
|
|
||||||
if startswith(line, "core id")
|
|
||||||
maxcore = max(maxcore, parse(Int, split(line, ':')[2]))
|
|
||||||
end
|
|
||||||
end
|
|
||||||
maxcore < 0 && error("failure to read core ids from /proc/cpuinfo")
|
|
||||||
return maxcore + 1
|
|
||||||
end
|
|
||||||
|
|
||||||
function parse_commandline()
|
|
||||||
s = ArgParseSettings()
|
|
||||||
|
|
||||||
@add_arg_table s begin
|
|
||||||
"--tol"
|
|
||||||
help = "set numerical tolerance for the SDP solver"
|
|
||||||
arg_type = Float64
|
|
||||||
default = 1e-6
|
|
||||||
"--iterations"
|
|
||||||
help = "set maximal number of iterations for the SDP solver"
|
|
||||||
arg_type = Int
|
|
||||||
default = 20000
|
|
||||||
"--upper-bound"
|
|
||||||
help = "Set an upper bound for the spectral gap"
|
|
||||||
arg_type = Float64
|
|
||||||
default = Inf
|
|
||||||
"--cpus"
|
|
||||||
help = "Set number of cpus used by solver (default: auto)"
|
|
||||||
arg_type = Int
|
|
||||||
required = false
|
|
||||||
"-N"
|
|
||||||
help = "Consider automorphisms of free group on N generators"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
end
|
|
||||||
|
|
||||||
return parse_args(s)
|
|
||||||
end
|
|
||||||
|
|
||||||
function main()
|
|
||||||
|
|
||||||
parsed_args = parse_commandline()
|
|
||||||
if parsed_args["cpus"] ≠ nothing
|
|
||||||
if parsed_args["cpus"] > cpuinfo_physicalcores()
|
|
||||||
warn("Number of specified cores exceeds the physical core cound. Performance will suffer.")
|
|
||||||
end
|
|
||||||
Blas.set_num_threads(parsed_args["cpus"])
|
|
||||||
end
|
|
||||||
|
|
||||||
N = parsed_args["N"]
|
|
||||||
radius = 2
|
|
||||||
tol = parsed_args["tol"]
|
|
||||||
iterations = parsed_args["iterations"]
|
|
||||||
upper_bound = parsed_args["upper-bound"]
|
|
||||||
|
|
||||||
dirname = "SOutF$(N)_$(upper_bound)_r=$radius"
|
|
||||||
|
|
||||||
logger = PropertyT.setup_logging(dirname)
|
|
||||||
|
|
||||||
info(logger, "Group: $dirname")
|
|
||||||
info(logger, "Iterations: $iterations")
|
|
||||||
info(logger, "Precision: $tol")
|
|
||||||
info(logger, "Upper bound: $upper_bound")
|
|
||||||
|
|
||||||
G, S = SOutFN_generating_set(N)
|
|
||||||
info(logger, G)
|
|
||||||
info(logger, "Symmetric generating set of size $(length(S))")
|
|
||||||
info(logger, S)
|
|
||||||
Id = G()
|
|
||||||
|
|
||||||
solver = SCSSolver(eps=tol, max_iters=iterations, linearsolver=SCS.Direct)
|
|
||||||
|
|
||||||
@time PropertyT.check_property_T(dirname, S, Id, solver, upper_bound, tol, 2)
|
|
||||||
return 0
|
|
||||||
end
|
|
||||||
|
|
||||||
main()
|
|
@ -1,51 +0,0 @@
|
|||||||
using ArgParse
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Parsing command line
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function parse_commandline()
|
|
||||||
settings = ArgParseSettings()
|
|
||||||
|
|
||||||
@add_arg_table settings begin
|
|
||||||
"--tol"
|
|
||||||
help = "set numerical tolerance for the SDP solver"
|
|
||||||
arg_type = Float64
|
|
||||||
default = 1e-14
|
|
||||||
"--iterations"
|
|
||||||
help = "set maximal number of iterations for the SDP solver (default: 20000)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 60000
|
|
||||||
"--upper-bound"
|
|
||||||
help = "Set an upper bound for the spectral gap"
|
|
||||||
arg_type = Float64
|
|
||||||
default = Inf
|
|
||||||
"--cpus"
|
|
||||||
help = "Set number of cpus used by solver (default: auto)"
|
|
||||||
arg_type = Int
|
|
||||||
required = false
|
|
||||||
"-N"
|
|
||||||
help = "Consider automorphisms of free group on N generators"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
"--radius"
|
|
||||||
help = "Radius of ball B_r(e,S) to find solution over"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
end
|
|
||||||
|
|
||||||
return parse_args(settings)
|
|
||||||
end
|
|
||||||
|
|
||||||
parsed_args = parse_commandline()
|
|
||||||
|
|
||||||
include("CPUselect.jl")
|
|
||||||
|
|
||||||
set_parallel_mthread(parsed_args)
|
|
||||||
|
|
||||||
include("SAutFNs.jl")
|
|
||||||
include("Orbit.jl")
|
|
||||||
|
|
||||||
main(SAutFNs, parsed_args)
|
|
27
CPUselect.jl
27
CPUselect.jl
@ -9,22 +9,27 @@ function cpuinfo_physicalcores()
|
|||||||
return maxcore + 1
|
return maxcore + 1
|
||||||
end
|
end
|
||||||
|
|
||||||
function set_parallel_mthread(parsed_args)
|
function set_parallel_mthread(N::Int, workers::Bool)
|
||||||
|
if N > cpuinfo_physicalcores()
|
||||||
|
warn("Number of specified cores exceeds the physical core count. Performance may suffer.")
|
||||||
|
end
|
||||||
|
|
||||||
|
if workers
|
||||||
|
addprocs(N)
|
||||||
|
info("Using $N cpus in @parallel code.")
|
||||||
|
end
|
||||||
|
info("Using $(Threads.nthreads()) threads in @threads code.")
|
||||||
|
BLAS.set_num_threads(N)
|
||||||
|
info("Using $N threads in BLAS.")
|
||||||
|
|
||||||
|
end
|
||||||
|
|
||||||
|
function set_parallel_mthread(parsed_args::Dict; workers=false)
|
||||||
if parsed_args["cpus"] == nothing
|
if parsed_args["cpus"] == nothing
|
||||||
N = cpuinfo_physicalcores()
|
N = cpuinfo_physicalcores()
|
||||||
else
|
else
|
||||||
N = parsed_args["cpus"]
|
N = parsed_args["cpus"]
|
||||||
if N > cpuinfo_physicalcores()
|
|
||||||
warn("Number of specified cores exceeds the physical core count. Performance may suffer.")
|
|
||||||
end
|
|
||||||
end
|
end
|
||||||
|
|
||||||
info("Using $N cpus in @parallel code.")
|
set_parallel_mthread(N, workers)
|
||||||
info("Using $(Threads.nthreads()) threads in @threads code.")
|
|
||||||
|
|
||||||
addprocs(N)
|
|
||||||
BLAS.set_num_threads(N)
|
|
||||||
|
|
||||||
return N
|
|
||||||
end
|
end
|
||||||
|
157
FPGroups_GAP.jl
Normal file
157
FPGroups_GAP.jl
Normal file
@ -0,0 +1,157 @@
|
|||||||
|
using JLD
|
||||||
|
|
||||||
|
function GAP_code(group_code, dir, R; maxeqns=10_000, infolevel=2)
|
||||||
|
code = """
|
||||||
|
LogTo("$(dir)/GAP.log");
|
||||||
|
RequirePackage("kbmag");
|
||||||
|
SetInfoLevel(InfoRWS, $infolevel);
|
||||||
|
|
||||||
|
|
||||||
|
MetricBalls := function(rws, R)
|
||||||
|
local l, basis, sizes, i;
|
||||||
|
l := EnumerateReducedWords(rws, 0, R);;
|
||||||
|
SortBy(l, Length);
|
||||||
|
sizes := [1..R];
|
||||||
|
Apply(sizes, i -> Number(l, w -> Length(w) <= i));
|
||||||
|
return [l, sizes];
|
||||||
|
end;;
|
||||||
|
|
||||||
|
ProductMatrix := function(rws, basis, len)
|
||||||
|
local result, dict, g, tmpList, t;
|
||||||
|
result := [];
|
||||||
|
dict := NewDictionary(basis[1], true);
|
||||||
|
t := Runtime();
|
||||||
|
for g in [1..Length(basis)] do;
|
||||||
|
AddDictionary(dict, basis[g], g);
|
||||||
|
od;
|
||||||
|
Print("Creating dictionary: \t\t", StringTime(Runtime()-t), "\\n");
|
||||||
|
for g in basis{[1..len]} do;
|
||||||
|
tmpList := List(Inverse(g)*basis{[1..len]}, w->ReducedForm(rws, w));
|
||||||
|
#t := Runtime();
|
||||||
|
tmpList := List(tmpList, x -> LookupDictionary(dict, x));
|
||||||
|
#Print(Runtime()-t, "\\n");
|
||||||
|
Assert(1, ForAll(tmpList, x -> x <> fail));
|
||||||
|
Add(result, tmpList);
|
||||||
|
od;
|
||||||
|
return result;
|
||||||
|
end;;
|
||||||
|
|
||||||
|
SaveCSV := function(fname, pm)
|
||||||
|
local file, i, j, k;
|
||||||
|
file := OutputTextFile(fname, false);;
|
||||||
|
for i in pm do;
|
||||||
|
k := 1;
|
||||||
|
for j in i do;
|
||||||
|
if k < Length(i) then
|
||||||
|
AppendTo(file, j, ", ");
|
||||||
|
else
|
||||||
|
AppendTo(file, j, "\\n");
|
||||||
|
fi;
|
||||||
|
k := k+1;
|
||||||
|
od;
|
||||||
|
od;
|
||||||
|
CloseStream(file);
|
||||||
|
end;;
|
||||||
|
|
||||||
|
$group_code
|
||||||
|
|
||||||
|
# G:= SimplifiedFpGroup(G);
|
||||||
|
RWS := KBMAGRewritingSystem(G);
|
||||||
|
# ResetRewritingSystem(RWS);
|
||||||
|
O:=OptionsRecordOfKBMAGRewritingSystem(RWS);;
|
||||||
|
O.maxeqns := $maxeqns;
|
||||||
|
O.maxstates := 1000*$maxeqns;
|
||||||
|
#O.maxstoredlen := [100,100];
|
||||||
|
|
||||||
|
before := Runtimes();;
|
||||||
|
KnuthBendix(RWS);
|
||||||
|
after := Runtimes();;
|
||||||
|
delta := after.user_time_children - before.user_time_children;;
|
||||||
|
Print("Knuth-Bendix completion: \t", StringTime(delta), "\\n");
|
||||||
|
|
||||||
|
t := Runtime();
|
||||||
|
res := MetricBalls(RWS,$(2*R));;
|
||||||
|
Print("Metric-Balls generation: \t", StringTime(Runtime()-t), "\\n");
|
||||||
|
B := res[1];; sizes := res[2];;
|
||||||
|
Print("Sizes of generated Balls: \t", sizes, "\\n");
|
||||||
|
|
||||||
|
t := Runtime();
|
||||||
|
pm := ProductMatrix(RWS, B, sizes[$R]);;
|
||||||
|
Print("Computing ProductMatrix: \t", StringTime(Runtime()-t), "\\n");
|
||||||
|
|
||||||
|
S := EnumerateReducedWords(RWS, 1, 1);
|
||||||
|
S := List(S, s -> Position(B,s));
|
||||||
|
|
||||||
|
SaveCSV("$(dir)/pm.csv", pm);
|
||||||
|
SaveCSV("$(dir)/S.csv", [S]);
|
||||||
|
SaveCSV("$(dir)/sizes.csv", [sizes]);
|
||||||
|
|
||||||
|
Print("DONE!\\n");
|
||||||
|
|
||||||
|
quit;""";
|
||||||
|
return code
|
||||||
|
end
|
||||||
|
|
||||||
|
function GAP_groupcode(S, rels)
|
||||||
|
F = "FreeGroup("*join(["\"$v\""for v in S], ", ") *");"
|
||||||
|
m = match(r".*(\[.*\])$", string(rels))
|
||||||
|
rels = replace(m.captures[1], " ", "\n")
|
||||||
|
code = """
|
||||||
|
F := $F;
|
||||||
|
AssignGeneratorVariables(F);;
|
||||||
|
relations := $rels;;
|
||||||
|
G := F/relations;
|
||||||
|
"""
|
||||||
|
return code
|
||||||
|
end
|
||||||
|
|
||||||
|
function GAP_execute(gap_code, dir)
|
||||||
|
isdir(dir) || mkdir(dir)
|
||||||
|
GAP_file = joinpath(dir, "GAP_code.g")
|
||||||
|
@show dir
|
||||||
|
@show GAP_file;
|
||||||
|
|
||||||
|
open(GAP_file, "w") do io
|
||||||
|
write(io, gap_code)
|
||||||
|
end
|
||||||
|
run(pipeline(`cat $(GAP_file)`, `gap -q`))
|
||||||
|
end
|
||||||
|
|
||||||
|
function prepare_pm_delta_csv(name, group_code, R; maxeqns=10_000, infolevel=2)
|
||||||
|
info("Preparing multiplication table using GAP (via kbmag)")
|
||||||
|
gap_code = GAP_code(group_code, name, R, maxeqns=maxeqns, infolevel=infolevel)
|
||||||
|
GAP_execute(gap_code, name)
|
||||||
|
end
|
||||||
|
|
||||||
|
function prepare_pm_delta(name, group_code, R; maxeqns=100_000, infolevel=2)
|
||||||
|
|
||||||
|
pm_fname = joinpath(name, "pm.csv")
|
||||||
|
S_fname = joinpath(name, "S.csv")
|
||||||
|
sizes_fname = joinpath(name, "sizes.csv")
|
||||||
|
delta_fname = joinpath(name, "delta.jld")
|
||||||
|
|
||||||
|
if !isfile(pm_fname) || !isfile(S_fname) || !isfile(sizes_fname)
|
||||||
|
prepare_pm_delta_csv(name, group_code, R, maxeqns=maxeqns, infolevel=infolevel)
|
||||||
|
end
|
||||||
|
|
||||||
|
if isfile(sizes_fname)
|
||||||
|
sizes = readcsv(sizes_fname, Int)[1,:]
|
||||||
|
if 2R > length(sizes)
|
||||||
|
prepare_pm_delta_csv(name, group_code, R, maxeqns=maxeqns, infolevel=infolevel)
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
pm = readcsv(pm_fname, Int)
|
||||||
|
S = readcsv(S_fname, Int)[1,:]
|
||||||
|
sizes = readcsv(sizes_fname, Int)[1,:]
|
||||||
|
|
||||||
|
Δ = spzeros(sizes[2R])
|
||||||
|
Δ[S] .= -1
|
||||||
|
Δ[1] = length(S)
|
||||||
|
|
||||||
|
pm = pm[1:sizes[R], 1:sizes[R]]
|
||||||
|
|
||||||
|
save(joinpath(name, "pm.jld"), "pm", pm)
|
||||||
|
save(joinpath(name, "delta.jld"), "Δ", Δ)
|
||||||
|
|
||||||
|
end
|
634
LICENSE.md
Normal file
634
LICENSE.md
Normal file
@ -0,0 +1,634 @@
|
|||||||
|
> Copyright (c) 2017: Marek Kaluba.
|
||||||
|
> This program is free software: you can redistribute it and/or modify
|
||||||
|
> it under the terms of the GNU General Public License as published by
|
||||||
|
> the Free Software Foundation, either version 3 of the License, or
|
||||||
|
> (at your option) any later version.
|
||||||
|
>
|
||||||
|
> This program is distributed in the hope that it will be useful,
|
||||||
|
> but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||||||
|
> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||||||
|
> GNU General Public License for more details.
|
||||||
|
>
|
||||||
|
>
|
||||||
|
> GNU GENERAL PUBLIC LICENSE
|
||||||
|
> Version 3, 29 June 2007
|
||||||
|
>
|
||||||
|
> Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>
|
||||||
|
> Everyone is permitted to copy and distribute verbatim copies
|
||||||
|
> of this license document, but changing it is not allowed.
|
||||||
|
>
|
||||||
|
> Preamble
|
||||||
|
>
|
||||||
|
> The GNU General Public License is a free, copyleft license for
|
||||||
|
> software and other kinds of works.
|
||||||
|
>
|
||||||
|
> The licenses for most software and other practical works are designed
|
||||||
|
> to take away your freedom to share and change the works. By contrast,
|
||||||
|
> the GNU General Public License is intended to guarantee your freedom to
|
||||||
|
> share and change all versions of a program--to make sure it remains free
|
||||||
|
> software for all its users. We, the Free Software Foundation, use the
|
||||||
|
> GNU General Public License for most of our software; it applies also to
|
||||||
|
> any other work released this way by its authors. You can apply it to
|
||||||
|
> your programs, too.
|
||||||
|
>
|
||||||
|
> When we speak of free software, we are referring to freedom, not
|
||||||
|
> price. Our General Public Licenses are designed to make sure that you
|
||||||
|
> have the freedom to distribute copies of free software (and charge for
|
||||||
|
> them if you wish), that you receive source code or can get it if you
|
||||||
|
> want it, that you can change the software or use pieces of it in new
|
||||||
|
> free programs, and that you know you can do these things.
|
||||||
|
>
|
||||||
|
> To protect your rights, we need to prevent others from denying you
|
||||||
|
> these rights or asking you to surrender the rights. Therefore, you have
|
||||||
|
> certain responsibilities if you distribute copies of the software, or if
|
||||||
|
> you modify it: responsibilities to respect the freedom of others.
|
||||||
|
>
|
||||||
|
> For example, if you distribute copies of such a program, whether
|
||||||
|
> gratis or for a fee, you must pass on to the recipients the same
|
||||||
|
> freedoms that you received. You must make sure that they, too, receive
|
||||||
|
> or can get the source code. And you must show them these terms so they
|
||||||
|
> know their rights.
|
||||||
|
>
|
||||||
|
> Developers that use the GNU GPL protect your rights with two steps:
|
||||||
|
> (1) assert copyright on the software, and (2) offer you this License
|
||||||
|
> giving you legal permission to copy, distribute and/or modify it.
|
||||||
|
>
|
||||||
|
> For the developers' and authors' protection, the GPL clearly explains
|
||||||
|
> that there is no warranty for this free software. For both users' and
|
||||||
|
> authors' sake, the GPL requires that modified versions be marked as
|
||||||
|
> changed, so that their problems will not be attributed erroneously to
|
||||||
|
> authors of previous versions.
|
||||||
|
>
|
||||||
|
> Some devices are designed to deny users access to install or run
|
||||||
|
> modified versions of the software inside them, although the manufacturer
|
||||||
|
> can do so. This is fundamentally incompatible with the aim of
|
||||||
|
> protecting users' freedom to change the software. The systematic
|
||||||
|
> pattern of such abuse occurs in the area of products for individuals to
|
||||||
|
> use, which is precisely where it is most unacceptable. Therefore, we
|
||||||
|
> have designed this version of the GPL to prohibit the practice for those
|
||||||
|
> products. If such problems arise substantially in other domains, we
|
||||||
|
> stand ready to extend this provision to those domains in future versions
|
||||||
|
> of the GPL, as needed to protect the freedom of users.
|
||||||
|
>
|
||||||
|
> Finally, every program is threatened constantly by software patents.
|
||||||
|
> States should not allow patents to restrict development and use of
|
||||||
|
> software on general-purpose computers, but in those that do, we wish to
|
||||||
|
> avoid the special danger that patents applied to a free program could
|
||||||
|
> make it effectively proprietary. To prevent this, the GPL assures that
|
||||||
|
> patents cannot be used to render the program non-free.
|
||||||
|
>
|
||||||
|
> The precise terms and conditions for copying, distribution and
|
||||||
|
> modification follow.
|
||||||
|
>
|
||||||
|
> TERMS AND CONDITIONS
|
||||||
|
>
|
||||||
|
> 0. Definitions.
|
||||||
|
>
|
||||||
|
> "This License" refers to version 3 of the GNU General Public License.
|
||||||
|
>
|
||||||
|
> "Copyright" also means copyright-like laws that apply to other kinds of
|
||||||
|
> works, such as semiconductor masks.
|
||||||
|
>
|
||||||
|
> "The Program" refers to any copyrightable work licensed under this
|
||||||
|
> License. Each licensee is addressed as "you". "Licensees" and
|
||||||
|
> "recipients" may be individuals or organizations.
|
||||||
|
>
|
||||||
|
> To "modify" a work means to copy from or adapt all or part of the work
|
||||||
|
> in a fashion requiring copyright permission, other than the making of an
|
||||||
|
> exact copy. The resulting work is called a "modified version" of the
|
||||||
|
> earlier work or a work "based on" the earlier work.
|
||||||
|
>
|
||||||
|
> A "covered work" means either the unmodified Program or a work based
|
||||||
|
> on the Program.
|
||||||
|
>
|
||||||
|
> To "propagate" a work means to do anything with it that, without
|
||||||
|
> permission, would make you directly or secondarily liable for
|
||||||
|
> infringement under applicable copyright law, except executing it on a
|
||||||
|
> computer or modifying a private copy. Propagation includes copying,
|
||||||
|
> distribution (with or without modification), making available to the
|
||||||
|
> public, and in some countries other activities as well.
|
||||||
|
>
|
||||||
|
> To "convey" a work means any kind of propagation that enables other
|
||||||
|
> parties to make or receive copies. Mere interaction with a user through
|
||||||
|
> a computer network, with no transfer of a copy, is not conveying.
|
||||||
|
>
|
||||||
|
> An interactive user interface displays "Appropriate Legal Notices"
|
||||||
|
> to the extent that it includes a convenient and prominently visible
|
||||||
|
> feature that (1) displays an appropriate copyright notice, and (2)
|
||||||
|
> tells the user that there is no warranty for the work (except to the
|
||||||
|
> extent that warranties are provided), that licensees may convey the
|
||||||
|
> work under this License, and how to view a copy of this License. If
|
||||||
|
> the interface presents a list of user commands or options, such as a
|
||||||
|
> menu, a prominent item in the list meets this criterion.
|
||||||
|
>
|
||||||
|
> 1. Source Code.
|
||||||
|
>
|
||||||
|
> The "source code" for a work means the preferred form of the work
|
||||||
|
> for making modifications to it. "Object code" means any non-source
|
||||||
|
> form of a work.
|
||||||
|
>
|
||||||
|
> A "Standard Interface" means an interface that either is an official
|
||||||
|
> standard defined by a recognized standards body, or, in the case of
|
||||||
|
> interfaces specified for a particular programming language, one that
|
||||||
|
> is widely used among developers working in that language.
|
||||||
|
>
|
||||||
|
> The "System Libraries" of an executable work include anything, other
|
||||||
|
> than the work as a whole, that (a) is included in the normal form of
|
||||||
|
> packaging a Major Component, but which is not part of that Major
|
||||||
|
> Component, and (b) serves only to enable use of the work with that
|
||||||
|
> Major Component, or to implement a Standard Interface for which an
|
||||||
|
> implementation is available to the public in source code form. A
|
||||||
|
> "Major Component", in this context, means a major essential component
|
||||||
|
> (kernel, window system, and so on) of the specific operating system
|
||||||
|
> (if any) on which the executable work runs, or a compiler used to
|
||||||
|
> produce the work, or an object code interpreter used to run it.
|
||||||
|
>
|
||||||
|
> The "Corresponding Source" for a work in object code form means all
|
||||||
|
> the source code needed to generate, install, and (for an executable
|
||||||
|
> work) run the object code and to modify the work, including scripts to
|
||||||
|
> control those activities. However, it does not include the work's
|
||||||
|
> System Libraries, or general-purpose tools or generally available free
|
||||||
|
> programs which are used unmodified in performing those activities but
|
||||||
|
> which are not part of the work. For example, Corresponding Source
|
||||||
|
> includes interface definition files associated with source files for
|
||||||
|
> the work, and the source code for shared libraries and dynamically
|
||||||
|
> linked subprograms that the work is specifically designed to require,
|
||||||
|
> such as by intimate data communication or control flow between those
|
||||||
|
> subprograms and other parts of the work.
|
||||||
|
>
|
||||||
|
> The Corresponding Source need not include anything that users
|
||||||
|
> can regenerate automatically from other parts of the Corresponding
|
||||||
|
> Source.
|
||||||
|
>
|
||||||
|
> The Corresponding Source for a work in source code form is that
|
||||||
|
> same work.
|
||||||
|
>
|
||||||
|
> 2. Basic Permissions.
|
||||||
|
>
|
||||||
|
> All rights granted under this License are granted for the term of
|
||||||
|
> copyright on the Program, and are irrevocable provided the stated
|
||||||
|
> conditions are met. This License explicitly affirms your unlimited
|
||||||
|
> permission to run the unmodified Program. The output from running a
|
||||||
|
> covered work is covered by this License only if the output, given its
|
||||||
|
> content, constitutes a covered work. This License acknowledges your
|
||||||
|
> rights of fair use or other equivalent, as provided by copyright law.
|
||||||
|
>
|
||||||
|
> You may make, run and propagate covered works that you do not
|
||||||
|
> convey, without conditions so long as your license otherwise remains
|
||||||
|
> in force. You may convey covered works to others for the sole purpose
|
||||||
|
> of having them make modifications exclusively for you, or provide you
|
||||||
|
> with facilities for running those works, provided that you comply with
|
||||||
|
> the terms of this License in conveying all material for which you do
|
||||||
|
> not control copyright. Those thus making or running the covered works
|
||||||
|
> for you must do so exclusively on your behalf, under your direction
|
||||||
|
> and control, on terms that prohibit them from making any copies of
|
||||||
|
> your copyrighted material outside their relationship with you.
|
||||||
|
>
|
||||||
|
> Conveying under any other circumstances is permitted solely under
|
||||||
|
> the conditions stated below. Sublicensing is not allowed; section 10
|
||||||
|
> makes it unnecessary.
|
||||||
|
>
|
||||||
|
> 3. Protecting Users' Legal Rights From Anti-Circumvention Law.
|
||||||
|
>
|
||||||
|
> No covered work shall be deemed part of an effective technological
|
||||||
|
> measure under any applicable law fulfilling obligations under article
|
||||||
|
> 11 of the WIPO copyright treaty adopted on 20 December 1996, or
|
||||||
|
> similar laws prohibiting or restricting circumvention of such
|
||||||
|
> measures.
|
||||||
|
>
|
||||||
|
> When you convey a covered work, you waive any legal power to forbid
|
||||||
|
> circumvention of technological measures to the extent such circumvention
|
||||||
|
> is effected by exercising rights under this License with respect to
|
||||||
|
> the covered work, and you disclaim any intention to limit operation or
|
||||||
|
> modification of the work as a means of enforcing, against the work's
|
||||||
|
> users, your or third parties' legal rights to forbid circumvention of
|
||||||
|
> technological measures.
|
||||||
|
>
|
||||||
|
> 4. Conveying Verbatim Copies.
|
||||||
|
>
|
||||||
|
> You may convey verbatim copies of the Program's source code as you
|
||||||
|
> receive it, in any medium, provided that you conspicuously and
|
||||||
|
> appropriately publish on each copy an appropriate copyright notice;
|
||||||
|
> keep intact all notices stating that this License and any
|
||||||
|
> non-permissive terms added in accord with section 7 apply to the code;
|
||||||
|
> keep intact all notices of the absence of any warranty; and give all
|
||||||
|
> recipients a copy of this License along with the Program.
|
||||||
|
>
|
||||||
|
> You may charge any price or no price for each copy that you convey,
|
||||||
|
> and you may offer support or warranty protection for a fee.
|
||||||
|
>
|
||||||
|
> 5. Conveying Modified Source Versions.
|
||||||
|
>
|
||||||
|
> You may convey a work based on the Program, or the modifications to
|
||||||
|
> produce it from the Program, in the form of source code under the
|
||||||
|
> terms of section 4, provided that you also meet all of these conditions:
|
||||||
|
>
|
||||||
|
> a) The work must carry prominent notices stating that you modified
|
||||||
|
> it, and giving a relevant date.
|
||||||
|
>
|
||||||
|
> b) The work must carry prominent notices stating that it is
|
||||||
|
> released under this License and any conditions added under section
|
||||||
|
> 7. This requirement modifies the requirement in section 4 to
|
||||||
|
> "keep intact all notices".
|
||||||
|
>
|
||||||
|
> c) You must license the entire work, as a whole, under this
|
||||||
|
> License to anyone who comes into possession of a copy. This
|
||||||
|
> License will therefore apply, along with any applicable section 7
|
||||||
|
> additional terms, to the whole of the work, and all its parts,
|
||||||
|
> regardless of how they are packaged. This License gives no
|
||||||
|
> permission to license the work in any other way, but it does not
|
||||||
|
> invalidate such permission if you have separately received it.
|
||||||
|
>
|
||||||
|
> d) If the work has interactive user interfaces, each must display
|
||||||
|
> Appropriate Legal Notices; however, if the Program has interactive
|
||||||
|
> interfaces that do not display Appropriate Legal Notices, your
|
||||||
|
> work need not make them do so.
|
||||||
|
>
|
||||||
|
> A compilation of a covered work with other separate and independent
|
||||||
|
> works, which are not by their nature extensions of the covered work,
|
||||||
|
> and which are not combined with it such as to form a larger program,
|
||||||
|
> in or on a volume of a storage or distribution medium, is called an
|
||||||
|
> "aggregate" if the compilation and its resulting copyright are not
|
||||||
|
> used to limit the access or legal rights of the compilation's users
|
||||||
|
> beyond what the individual works permit. Inclusion of a covered work
|
||||||
|
> in an aggregate does not cause this License to apply to the other
|
||||||
|
> parts of the aggregate.
|
||||||
|
>
|
||||||
|
> 6. Conveying Non-Source Forms.
|
||||||
|
>
|
||||||
|
> You may convey a covered work in object code form under the terms
|
||||||
|
> of sections 4 and 5, provided that you also convey the
|
||||||
|
> machine-readable Corresponding Source under the terms of this License,
|
||||||
|
> in one of these ways:
|
||||||
|
>
|
||||||
|
> a) Convey the object code in, or embodied in, a physical product
|
||||||
|
> (including a physical distribution medium), accompanied by the
|
||||||
|
> Corresponding Source fixed on a durable physical medium
|
||||||
|
> customarily used for software interchange.
|
||||||
|
>
|
||||||
|
> b) Convey the object code in, or embodied in, a physical product
|
||||||
|
> (including a physical distribution medium), accompanied by a
|
||||||
|
> written offer, valid for at least three years and valid for as
|
||||||
|
> long as you offer spare parts or customer support for that product
|
||||||
|
> model, to give anyone who possesses the object code either (1) a
|
||||||
|
> copy of the Corresponding Source for all the software in the
|
||||||
|
> product that is covered by this License, on a durable physical
|
||||||
|
> medium customarily used for software interchange, for a price no
|
||||||
|
> more than your reasonable cost of physically performing this
|
||||||
|
> conveying of source, or (2) access to copy the
|
||||||
|
> Corresponding Source from a network server at no charge.
|
||||||
|
>
|
||||||
|
> c) Convey individual copies of the object code with a copy of the
|
||||||
|
> written offer to provide the Corresponding Source. This
|
||||||
|
> alternative is allowed only occasionally and noncommercially, and
|
||||||
|
> only if you received the object code with such an offer, in accord
|
||||||
|
> with subsection 6b.
|
||||||
|
>
|
||||||
|
> d) Convey the object code by offering access from a designated
|
||||||
|
> place (gratis or for a charge), and offer equivalent access to the
|
||||||
|
> Corresponding Source in the same way through the same place at no
|
||||||
|
> further charge. You need not require recipients to copy the
|
||||||
|
> Corresponding Source along with the object code. If the place to
|
||||||
|
> copy the object code is a network server, the Corresponding Source
|
||||||
|
> may be on a different server (operated by you or a third party)
|
||||||
|
> that supports equivalent copying facilities, provided you maintain
|
||||||
|
> clear directions next to the object code saying where to find the
|
||||||
|
> Corresponding Source. Regardless of what server hosts the
|
||||||
|
> Corresponding Source, you remain obligated to ensure that it is
|
||||||
|
> available for as long as needed to satisfy these requirements.
|
||||||
|
>
|
||||||
|
> e) Convey the object code using peer-to-peer transmission, provided
|
||||||
|
> you inform other peers where the object code and Corresponding
|
||||||
|
> Source of the work are being offered to the general public at no
|
||||||
|
> charge under subsection 6d.
|
||||||
|
>
|
||||||
|
> A separable portion of the object code, whose source code is excluded
|
||||||
|
> from the Corresponding Source as a System Library, need not be
|
||||||
|
> included in conveying the object code work.
|
||||||
|
>
|
||||||
|
> A "User Product" is either (1) a "consumer product", which means any
|
||||||
|
> tangible personal property which is normally used for personal, family,
|
||||||
|
> or household purposes, or (2) anything designed or sold for incorporation
|
||||||
|
> into a dwelling. In determining whether a product is a consumer product,
|
||||||
|
> doubtful cases shall be resolved in favor of coverage. For a particular
|
||||||
|
> product received by a particular user, "normally used" refers to a
|
||||||
|
> typical or common use of that class of product, regardless of the status
|
||||||
|
> of the particular user or of the way in which the particular user
|
||||||
|
> actually uses, or expects or is expected to use, the product. A product
|
||||||
|
> is a consumer product regardless of whether the product has substantial
|
||||||
|
> commercial, industrial or non-consumer uses, unless such uses represent
|
||||||
|
> the only significant mode of use of the product.
|
||||||
|
>
|
||||||
|
> "Installation Information" for a User Product means any methods,
|
||||||
|
> procedures, authorization keys, or other information required to install
|
||||||
|
> and execute modified versions of a covered work in that User Product from
|
||||||
|
> a modified version of its Corresponding Source. The information must
|
||||||
|
> suffice to ensure that the continued functioning of the modified object
|
||||||
|
> code is in no case prevented or interfered with solely because
|
||||||
|
> modification has been made.
|
||||||
|
>
|
||||||
|
> If you convey an object code work under this section in, or with, or
|
||||||
|
> specifically for use in, a User Product, and the conveying occurs as
|
||||||
|
> part of a transaction in which the right of possession and use of the
|
||||||
|
> User Product is transferred to the recipient in perpetuity or for a
|
||||||
|
> fixed term (regardless of how the transaction is characterized), the
|
||||||
|
> Corresponding Source conveyed under this section must be accompanied
|
||||||
|
> by the Installation Information. But this requirement does not apply
|
||||||
|
> if neither you nor any third party retains the ability to install
|
||||||
|
> modified object code on the User Product (for example, the work has
|
||||||
|
> been installed in ROM).
|
||||||
|
>
|
||||||
|
> The requirement to provide Installation Information does not include a
|
||||||
|
> requirement to continue to provide support service, warranty, or updates
|
||||||
|
> for a work that has been modified or installed by the recipient, or for
|
||||||
|
> the User Product in which it has been modified or installed. Access to a
|
||||||
|
> network may be denied when the modification itself materially and
|
||||||
|
> adversely affects the operation of the network or violates the rules and
|
||||||
|
> protocols for communication across the network.
|
||||||
|
>
|
||||||
|
> Corresponding Source conveyed, and Installation Information provided,
|
||||||
|
> in accord with this section must be in a format that is publicly
|
||||||
|
> documented (and with an implementation available to the public in
|
||||||
|
> source code form), and must require no special password or key for
|
||||||
|
> unpacking, reading or copying.
|
||||||
|
>
|
||||||
|
> 7. Additional Terms.
|
||||||
|
>
|
||||||
|
> "Additional permissions" are terms that supplement the terms of this
|
||||||
|
> License by making exceptions from one or more of its conditions.
|
||||||
|
> Additional permissions that are applicable to the entire Program shall
|
||||||
|
> be treated as though they were included in this License, to the extent
|
||||||
|
> that they are valid under applicable law. If additional permissions
|
||||||
|
> apply only to part of the Program, that part may be used separately
|
||||||
|
> under those permissions, but the entire Program remains governed by
|
||||||
|
> this License without regard to the additional permissions.
|
||||||
|
>
|
||||||
|
> When you convey a copy of a covered work, you may at your option
|
||||||
|
> remove any additional permissions from that copy, or from any part of
|
||||||
|
> it. (Additional permissions may be written to require their own
|
||||||
|
> removal in certain cases when you modify the work.) You may place
|
||||||
|
> additional permissions on material, added by you to a covered work,
|
||||||
|
> for which you have or can give appropriate copyright permission.
|
||||||
|
>
|
||||||
|
> Notwithstanding any other provision of this License, for material you
|
||||||
|
> add to a covered work, you may (if authorized by the copyright holders of
|
||||||
|
> that material) supplement the terms of this License with terms:
|
||||||
|
>
|
||||||
|
> a) Disclaiming warranty or limiting liability differently from the
|
||||||
|
> terms of sections 15 and 16 of this License; or
|
||||||
|
>
|
||||||
|
> b) Requiring preservation of specified reasonable legal notices or
|
||||||
|
> author attributions in that material or in the Appropriate Legal
|
||||||
|
> Notices displayed by works containing it; or
|
||||||
|
>
|
||||||
|
> c) Prohibiting misrepresentation of the origin of that material, or
|
||||||
|
> requiring that modified versions of such material be marked in
|
||||||
|
> reasonable ways as different from the original version; or
|
||||||
|
>
|
||||||
|
> d) Limiting the use for publicity purposes of names of licensors or
|
||||||
|
> authors of the material; or
|
||||||
|
>
|
||||||
|
> e) Declining to grant rights under trademark law for use of some
|
||||||
|
> trade names, trademarks, or service marks; or
|
||||||
|
>
|
||||||
|
> f) Requiring indemnification of licensors and authors of that
|
||||||
|
> material by anyone who conveys the material (or modified versions of
|
||||||
|
> it) with contractual assumptions of liability to the recipient, for
|
||||||
|
> any liability that these contractual assumptions directly impose on
|
||||||
|
> those licensors and authors.
|
||||||
|
>
|
||||||
|
> All other non-permissive additional terms are considered "further
|
||||||
|
> restrictions" within the meaning of section 10. If the Program as you
|
||||||
|
> received it, or any part of it, contains a notice stating that it is
|
||||||
|
> governed by this License along with a term that is a further
|
||||||
|
> restriction, you may remove that term. If a license document contains
|
||||||
|
> a further restriction but permits relicensing or conveying under this
|
||||||
|
> License, you may add to a covered work material governed by the terms
|
||||||
|
> of that license document, provided that the further restriction does
|
||||||
|
> not survive such relicensing or conveying.
|
||||||
|
>
|
||||||
|
> If you add terms to a covered work in accord with this section, you
|
||||||
|
> must place, in the relevant source files, a statement of the
|
||||||
|
> additional terms that apply to those files, or a notice indicating
|
||||||
|
> where to find the applicable terms.
|
||||||
|
>
|
||||||
|
> Additional terms, permissive or non-permissive, may be stated in the
|
||||||
|
> form of a separately written license, or stated as exceptions;
|
||||||
|
> the above requirements apply either way.
|
||||||
|
>
|
||||||
|
> 8. Termination.
|
||||||
|
>
|
||||||
|
> You may not propagate or modify a covered work except as expressly
|
||||||
|
> provided under this License. Any attempt otherwise to propagate or
|
||||||
|
> modify it is void, and will automatically terminate your rights under
|
||||||
|
> this License (including any patent licenses granted under the third
|
||||||
|
> paragraph of section 11).
|
||||||
|
>
|
||||||
|
> However, if you cease all violation of this License, then your
|
||||||
|
> license from a particular copyright holder is reinstated (a)
|
||||||
|
> provisionally, unless and until the copyright holder explicitly and
|
||||||
|
> finally terminates your license, and (b) permanently, if the copyright
|
||||||
|
> holder fails to notify you of the violation by some reasonable means
|
||||||
|
> prior to 60 days after the cessation.
|
||||||
|
>
|
||||||
|
> Moreover, your license from a particular copyright holder is
|
||||||
|
> reinstated permanently if the copyright holder notifies you of the
|
||||||
|
> violation by some reasonable means, this is the first time you have
|
||||||
|
> received notice of violation of this License (for any work) from that
|
||||||
|
> copyright holder, and you cure the violation prior to 30 days after
|
||||||
|
> your receipt of the notice.
|
||||||
|
>
|
||||||
|
> Termination of your rights under this section does not terminate the
|
||||||
|
> licenses of parties who have received copies or rights from you under
|
||||||
|
> this License. If your rights have been terminated and not permanently
|
||||||
|
> reinstated, you do not qualify to receive new licenses for the same
|
||||||
|
> material under section 10.
|
||||||
|
>
|
||||||
|
> 9. Acceptance Not Required for Having Copies.
|
||||||
|
>
|
||||||
|
> You are not required to accept this License in order to receive or
|
||||||
|
> run a copy of the Program. Ancillary propagation of a covered work
|
||||||
|
> occurring solely as a consequence of using peer-to-peer transmission
|
||||||
|
> to receive a copy likewise does not require acceptance. However,
|
||||||
|
> nothing other than this License grants you permission to propagate or
|
||||||
|
> modify any covered work. These actions infringe copyright if you do
|
||||||
|
> not accept this License. Therefore, by modifying or propagating a
|
||||||
|
> covered work, you indicate your acceptance of this License to do so.
|
||||||
|
>
|
||||||
|
> 10. Automatic Licensing of Downstream Recipients.
|
||||||
|
>
|
||||||
|
> Each time you convey a covered work, the recipient automatically
|
||||||
|
> receives a license from the original licensors, to run, modify and
|
||||||
|
> propagate that work, subject to this License. You are not responsible
|
||||||
|
> for enforcing compliance by third parties with this License.
|
||||||
|
>
|
||||||
|
> An "entity transaction" is a transaction transferring control of an
|
||||||
|
> organization, or substantially all assets of one, or subdividing an
|
||||||
|
> organization, or merging organizations. If propagation of a covered
|
||||||
|
> work results from an entity transaction, each party to that
|
||||||
|
> transaction who receives a copy of the work also receives whatever
|
||||||
|
> licenses to the work the party's predecessor in interest had or could
|
||||||
|
> give under the previous paragraph, plus a right to possession of the
|
||||||
|
> Corresponding Source of the work from the predecessor in interest, if
|
||||||
|
> the predecessor has it or can get it with reasonable efforts.
|
||||||
|
>
|
||||||
|
> You may not impose any further restrictions on the exercise of the
|
||||||
|
> rights granted or affirmed under this License. For example, you may
|
||||||
|
> not impose a license fee, royalty, or other charge for exercise of
|
||||||
|
> rights granted under this License, and you may not initiate litigation
|
||||||
|
> (including a cross-claim or counterclaim in a lawsuit) alleging that
|
||||||
|
> any patent claim is infringed by making, using, selling, offering for
|
||||||
|
> sale, or importing the Program or any portion of it.
|
||||||
|
>
|
||||||
|
> 11. Patents.
|
||||||
|
>
|
||||||
|
> A "contributor" is a copyright holder who authorizes use under this
|
||||||
|
> License of the Program or a work on which the Program is based. The
|
||||||
|
> work thus licensed is called the contributor's "contributor version".
|
||||||
|
>
|
||||||
|
> A contributor's "essential patent claims" are all patent claims
|
||||||
|
> owned or controlled by the contributor, whether already acquired or
|
||||||
|
> hereafter acquired, that would be infringed by some manner, permitted
|
||||||
|
> by this License, of making, using, or selling its contributor version,
|
||||||
|
> but do not include claims that would be infringed only as a
|
||||||
|
> consequence of further modification of the contributor version. For
|
||||||
|
> purposes of this definition, "control" includes the right to grant
|
||||||
|
> patent sublicenses in a manner consistent with the requirements of
|
||||||
|
> this License.
|
||||||
|
>
|
||||||
|
> Each contributor grants you a non-exclusive, worldwide, royalty-free
|
||||||
|
> patent license under the contributor's essential patent claims, to
|
||||||
|
> make, use, sell, offer for sale, import and otherwise run, modify and
|
||||||
|
> propagate the contents of its contributor version.
|
||||||
|
>
|
||||||
|
> In the following three paragraphs, a "patent license" is any express
|
||||||
|
> agreement or commitment, however denominated, not to enforce a patent
|
||||||
|
> (such as an express permission to practice a patent or covenant not to
|
||||||
|
> sue for patent infringement). To "grant" such a patent license to a
|
||||||
|
> party means to make such an agreement or commitment not to enforce a
|
||||||
|
> patent against the party.
|
||||||
|
>
|
||||||
|
> If you convey a covered work, knowingly relying on a patent license,
|
||||||
|
> and the Corresponding Source of the work is not available for anyone
|
||||||
|
> to copy, free of charge and under the terms of this License, through a
|
||||||
|
> publicly available network server or other readily accessible means,
|
||||||
|
> then you must either (1) cause the Corresponding Source to be so
|
||||||
|
> available, or (2) arrange to deprive yourself of the benefit of the
|
||||||
|
> patent license for this particular work, or (3) arrange, in a manner
|
||||||
|
> consistent with the requirements of this License, to extend the patent
|
||||||
|
> license to downstream recipients. "Knowingly relying" means you have
|
||||||
|
> actual knowledge that, but for the patent license, your conveying the
|
||||||
|
> covered work in a country, or your recipient's use of the covered work
|
||||||
|
> in a country, would infringe one or more identifiable patents in that
|
||||||
|
> country that you have reason to believe are valid.
|
||||||
|
>
|
||||||
|
> If, pursuant to or in connection with a single transaction or
|
||||||
|
> arrangement, you convey, or propagate by procuring conveyance of, a
|
||||||
|
> covered work, and grant a patent license to some of the parties
|
||||||
|
> receiving the covered work authorizing them to use, propagate, modify
|
||||||
|
> or convey a specific copy of the covered work, then the patent license
|
||||||
|
> you grant is automatically extended to all recipients of the covered
|
||||||
|
> work and works based on it.
|
||||||
|
>
|
||||||
|
> A patent license is "discriminatory" if it does not include within
|
||||||
|
> the scope of its coverage, prohibits the exercise of, or is
|
||||||
|
> conditioned on the non-exercise of one or more of the rights that are
|
||||||
|
> specifically granted under this License. You may not convey a covered
|
||||||
|
> work if you are a party to an arrangement with a third party that is
|
||||||
|
> in the business of distributing software, under which you make payment
|
||||||
|
> to the third party based on the extent of your activity of conveying
|
||||||
|
> the work, and under which the third party grants, to any of the
|
||||||
|
> parties who would receive the covered work from you, a discriminatory
|
||||||
|
> patent license (a) in connection with copies of the covered work
|
||||||
|
> conveyed by you (or copies made from those copies), or (b) primarily
|
||||||
|
> for and in connection with specific products or compilations that
|
||||||
|
> contain the covered work, unless you entered into that arrangement,
|
||||||
|
> or that patent license was granted, prior to 28 March 2007.
|
||||||
|
>
|
||||||
|
> Nothing in this License shall be construed as excluding or limiting
|
||||||
|
> any implied license or other defenses to infringement that may
|
||||||
|
> otherwise be available to you under applicable patent law.
|
||||||
|
>
|
||||||
|
> 12. No Surrender of Others' Freedom.
|
||||||
|
>
|
||||||
|
> If conditions are imposed on you (whether by court order, agreement or
|
||||||
|
> otherwise) that contradict the conditions of this License, they do not
|
||||||
|
> excuse you from the conditions of this License. If you cannot convey a
|
||||||
|
> covered work so as to satisfy simultaneously your obligations under this
|
||||||
|
> License and any other pertinent obligations, then as a consequence you may
|
||||||
|
> not convey it at all. For example, if you agree to terms that obligate you
|
||||||
|
> to collect a royalty for further conveying from those to whom you convey
|
||||||
|
> the Program, the only way you could satisfy both those terms and this
|
||||||
|
> License would be to refrain entirely from conveying the Program.
|
||||||
|
>
|
||||||
|
> 13. Use with the GNU Affero General Public License.
|
||||||
|
>
|
||||||
|
> Notwithstanding any other provision of this License, you have
|
||||||
|
> permission to link or combine any covered work with a work licensed
|
||||||
|
> under version 3 of the GNU Affero General Public License into a single
|
||||||
|
> combined work, and to convey the resulting work. The terms of this
|
||||||
|
> License will continue to apply to the part which is the covered work,
|
||||||
|
> but the special requirements of the GNU Affero General Public License,
|
||||||
|
> section 13, concerning interaction through a network will apply to the
|
||||||
|
> combination as such.
|
||||||
|
>
|
||||||
|
> 14. Revised Versions of this License.
|
||||||
|
>
|
||||||
|
> The Free Software Foundation may publish revised and/or new versions of
|
||||||
|
> the GNU General Public License from time to time. Such new versions will
|
||||||
|
> be similar in spirit to the present version, but may differ in detail to
|
||||||
|
> address new problems or concerns.
|
||||||
|
>
|
||||||
|
> Each version is given a distinguishing version number. If the
|
||||||
|
> Program specifies that a certain numbered version of the GNU General
|
||||||
|
> Public License "or any later version" applies to it, you have the
|
||||||
|
> option of following the terms and conditions either of that numbered
|
||||||
|
> version or of any later version published by the Free Software
|
||||||
|
> Foundation. If the Program does not specify a version number of the
|
||||||
|
> GNU General Public License, you may choose any version ever published
|
||||||
|
> by the Free Software Foundation.
|
||||||
|
>
|
||||||
|
> If the Program specifies that a proxy can decide which future
|
||||||
|
> versions of the GNU General Public License can be used, that proxy's
|
||||||
|
> public statement of acceptance of a version permanently authorizes you
|
||||||
|
> to choose that version for the Program.
|
||||||
|
>
|
||||||
|
> Later license versions may give you additional or different
|
||||||
|
> permissions. However, no additional obligations are imposed on any
|
||||||
|
> author or copyright holder as a result of your choosing to follow a
|
||||||
|
> later version.
|
||||||
|
>
|
||||||
|
> 15. Disclaimer of Warranty.
|
||||||
|
>
|
||||||
|
> THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY
|
||||||
|
> APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT
|
||||||
|
> HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY
|
||||||
|
> OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
|
||||||
|
> THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
||||||
|
> PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM
|
||||||
|
> IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF
|
||||||
|
> ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
|
||||||
|
>
|
||||||
|
> 16. Limitation of Liability.
|
||||||
|
>
|
||||||
|
> IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
|
||||||
|
> WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS
|
||||||
|
> THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY
|
||||||
|
> GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
|
||||||
|
> USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF
|
||||||
|
> DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD
|
||||||
|
> PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),
|
||||||
|
> EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
|
||||||
|
> SUCH DAMAGES.
|
||||||
|
>
|
||||||
|
> 17. Interpretation of Sections 15 and 16.
|
||||||
|
>
|
||||||
|
> If the disclaimer of warranty and limitation of liability provided
|
||||||
|
> above cannot be given local legal effect according to their terms,
|
||||||
|
> reviewing courts shall apply local law that most closely approximates
|
||||||
|
> an absolute waiver of all civil liability in connection with the
|
||||||
|
> Program, unless a warranty or assumption of liability accompanies a
|
||||||
|
> copy of the Program in return for a fee.
|
||||||
|
>
|
||||||
|
> END OF TERMS AND CONDITIONS
|
||||||
|
>
|
44
Orbit.jl
44
Orbit.jl
@ -1,44 +0,0 @@
|
|||||||
using SCS.SCSSolver
|
|
||||||
# using Mosek
|
|
||||||
|
|
||||||
using Nemo
|
|
||||||
|
|
||||||
using PropertyT
|
|
||||||
using Groups
|
|
||||||
|
|
||||||
function main(GROUP, parsed_args)
|
|
||||||
|
|
||||||
radius = parsed_args["radius"]
|
|
||||||
tol = parsed_args["tol"]
|
|
||||||
iterations = parsed_args["iterations"]
|
|
||||||
upper_bound = parsed_args["upper-bound"]
|
|
||||||
|
|
||||||
name, N = GROUP.groupname(parsed_args)
|
|
||||||
G, S = GROUP.generatingset(parsed_args)
|
|
||||||
AutS = GROUP.autS(parsed_args)
|
|
||||||
|
|
||||||
name = "$(name)_r$radius"
|
|
||||||
isdir(name) || mkdir(name)
|
|
||||||
|
|
||||||
logger = PropertyT.setup_logging(joinpath(name, "$(upper_bound)"))
|
|
||||||
|
|
||||||
info(logger, "Group: $name")
|
|
||||||
info(logger, "Iterations: $iterations")
|
|
||||||
info(logger, "Precision: $tol")
|
|
||||||
info(logger, "Upper bound: $upper_bound")
|
|
||||||
info(logger, "Threads: $(Threads.nthreads())")
|
|
||||||
info(logger, "Workers: $(workers())")
|
|
||||||
info(logger, G)
|
|
||||||
info(logger, "Symmetric generating set of size $(length(S))")
|
|
||||||
# info(logger, S)
|
|
||||||
|
|
||||||
solver = SCSSolver(eps=tol, max_iters=iterations, linearsolver=SCS.Direct)
|
|
||||||
# solver = Mosek.MosekSolver(
|
|
||||||
# MSK_DPAR_INTPNT_CO_TOL_REL_GAP=tol,
|
|
||||||
# MSK_IPAR_INTPNT_MAX_ITERATIONS=iterations,
|
|
||||||
# QUIET=false)
|
|
||||||
|
|
||||||
sett = Settings(name, N, G, S, AutS, radius, solver, upper_bound, tol)
|
|
||||||
|
|
||||||
PropertyT.check_property_T(sett)
|
|
||||||
end
|
|
64
README.md
64
README.md
@ -1,4 +1,10 @@
|
|||||||
This repository contains code for computations in [Certifying Numerical Estimates of Spectral Gaps](https://arxiv.org/abs/1703.09680).
|
# 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
|
# Installing
|
||||||
To run the code You need `julia-v0.5` (should work on `v0.6`, but with warnings).
|
To run the code You need `julia-v0.5` (should work on `v0.6`, but with warnings).
|
||||||
@ -23,6 +29,8 @@ cd GroupswithPropertyT
|
|||||||
|
|
||||||
# Running
|
# 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
|
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
|
```shell
|
||||||
julia SL.jl -N 2 -p 7 --radius 2 --iterations 100000
|
julia SL.jl -N 2 -p 7 --radius 2 --iterations 100000
|
||||||
@ -39,7 +47,24 @@ If You see in the output (or in `full.log`) that the upper end of the interval w
|
|||||||
```
|
```
|
||||||
julia SL.jl -N 2 -p 7 --radius 3 --iterations 100000 --tol 1e-9
|
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))\|*tol$)
|
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
|
# Help
|
||||||
|
|
||||||
@ -70,7 +95,7 @@ optional arguments:
|
|||||||
-h, --help show this help message and exit
|
-h, --help show this help message and exit
|
||||||
```
|
```
|
||||||
|
|
||||||
# Specific version of the article
|
# 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`)
|
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
|
```shell
|
||||||
@ -83,3 +108,36 @@ Pkg.checkout("GroupRings", "1703.09680v1")
|
|||||||
Pkg.checkout("PropertyT", "1703.09680v1")
|
Pkg.checkout("PropertyT", "1703.09680v1")
|
||||||
Pkg.resolve()
|
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.
|
||||||
|
78
SAutFNs.jl
78
SAutFNs.jl
@ -1,78 +0,0 @@
|
|||||||
module SAutFNs
|
|
||||||
|
|
||||||
using Nemo
|
|
||||||
using Groups
|
|
||||||
|
|
||||||
if VERSION >= v"0.6.0"
|
|
||||||
import Nemo.Generic.perm
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Generating set
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function generatingset(N::Int)
|
|
||||||
|
|
||||||
SAutFN = AutGroup(FreeGroup(N), special=true)
|
|
||||||
S = gens(SAutFN);
|
|
||||||
S = [S; [inv(s) for s in S]]
|
|
||||||
|
|
||||||
return SAutFN, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
function generatingset(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
return generatingset(N)
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Action of WreathProductElems on AutGroupElem
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function AutFG_emb(A::AutGroup, g::WreathProductElem)
|
|
||||||
isa(A.objectGroup, FreeGroup) || throw("Not an Aut(Fₙ)")
|
|
||||||
parent(g).P.n == length(A.objectGroup.gens) || throw("No natural embedding of $(parent(g)) into $A")
|
|
||||||
powers = [(elt == parent(elt)() ? 0: 1) for elt in g.n.elts]
|
|
||||||
elt = reduce(*, [A(Groups.flip_autsymbol(i))^pow for (i,pow) in enumerate(powers)])
|
|
||||||
Groups.r_multiply!(elt, [Groups.perm_autsymbol(g.p)])
|
|
||||||
return elt
|
|
||||||
end
|
|
||||||
|
|
||||||
function AutFG_emb(A::AutGroup, p::perm)
|
|
||||||
isa(A.objectGroup, FreeGroup) || throw("Not an Aut(Fₙ)")
|
|
||||||
parent(p).n == length(A.objectGroup.gens) || throw("No natural embedding of $(parent(g)) into $A")
|
|
||||||
return A(Groups.perm_autsymbol(p))
|
|
||||||
end
|
|
||||||
|
|
||||||
function (g::WreathProductElem)(a::AutGroupElem)
|
|
||||||
g = AutFG_emb(parent(a),g)
|
|
||||||
return g*a*g^-1
|
|
||||||
end
|
|
||||||
|
|
||||||
function (p::perm)(a::AutGroupElem)
|
|
||||||
g = AutFG_emb(parent(a),p)
|
|
||||||
return g*a*g^-1
|
|
||||||
end
|
|
||||||
|
|
||||||
function autS(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
return WreathProduct(PermutationGroup(2), PermutationGroup(N))
|
|
||||||
# return WreathProduct(FiniteField(2,1, "a")[1], PermutationGroup(N))
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Misc
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function groupname(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
return "oSAutF$(N)", N
|
|
||||||
end
|
|
||||||
|
|
||||||
end # of module SAutFNs
|
|
151
SL.jl
151
SL.jl
@ -1,151 +0,0 @@
|
|||||||
using ArgParse
|
|
||||||
|
|
||||||
using Nemo
|
|
||||||
import SCS.SCSSolver
|
|
||||||
using PropertyT
|
|
||||||
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Generating set
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function E(i::Int, j::Int, M::MatSpace, val=one(M.base_ring))
|
|
||||||
@assert i≠j
|
|
||||||
m = one(M)
|
|
||||||
m[i,j] = val
|
|
||||||
return m
|
|
||||||
end
|
|
||||||
|
|
||||||
function SLsize(n,p)
|
|
||||||
result = BigInt(1)
|
|
||||||
for k in 0:n-1
|
|
||||||
result *= p^n - p^k
|
|
||||||
end
|
|
||||||
return div(result, p-1)
|
|
||||||
end
|
|
||||||
|
|
||||||
function SL_generatingset(n::Int, X::Bool=false)
|
|
||||||
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
|
||||||
G = MatrixSpace(ZZ, n, n)
|
|
||||||
if X
|
|
||||||
S = [E(i,j,G,v) for (i,j) in indexing for v in [1, 100]]
|
|
||||||
else
|
|
||||||
S = [E(i,j,G,v) for (i,j) in indexing for v in [1]]
|
|
||||||
end
|
|
||||||
S = vcat(S, [inv(x) for x in S])
|
|
||||||
return G, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
function SL_generatingset(n::Int, p::Int, X::Bool=false)
|
|
||||||
p == 0 && return SL_generatingset(n, X)
|
|
||||||
(p > 1 && n > 1) || throw("Both n and p should be positive integers!")
|
|
||||||
info("Size(SL($n,$p)) = $(SLsize(n,p))")
|
|
||||||
F = ResidueRing(ZZ, p)
|
|
||||||
G = MatrixSpace(F, n, n)
|
|
||||||
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
|
||||||
S = [E(i, j, G) for (i,j) in indexing]
|
|
||||||
S = vcat(S, [inv(x) for x in S])
|
|
||||||
return G, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Parsing command line
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function cpuinfo_physicalcores()
|
|
||||||
maxcore = -1
|
|
||||||
for line in eachline("/proc/cpuinfo")
|
|
||||||
if startswith(line, "core id")
|
|
||||||
maxcore = max(maxcore, parse(Int, split(line, ':')[2]))
|
|
||||||
end
|
|
||||||
end
|
|
||||||
maxcore < 0 && error("failure to read core ids from /proc/cpuinfo")
|
|
||||||
return maxcore + 1
|
|
||||||
end
|
|
||||||
|
|
||||||
function parse_commandline()
|
|
||||||
settings = ArgParseSettings()
|
|
||||||
|
|
||||||
@add_arg_table settings begin
|
|
||||||
"--tol"
|
|
||||||
help = "set numerical tolerance for the SDP solver"
|
|
||||||
arg_type = Float64
|
|
||||||
default = 1e-6
|
|
||||||
"--iterations"
|
|
||||||
help = "set maximal number of iterations for the SDP solver (default: 20000)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 50000
|
|
||||||
"--upper-bound"
|
|
||||||
help = "Set an upper bound for the spectral gap"
|
|
||||||
arg_type = Float64
|
|
||||||
default = Inf
|
|
||||||
"--cpus"
|
|
||||||
help = "Set number of cpus used by solver"
|
|
||||||
arg_type = Int
|
|
||||||
required = false
|
|
||||||
"-N"
|
|
||||||
help = "Consider elementary matrices EL(N)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
"-p"
|
|
||||||
help = "Matrices over field of p-elements (p=0 => over ZZ)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 0
|
|
||||||
"--radius"
|
|
||||||
help = "Radius of ball B_r(e,S) to find solution over"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
end
|
|
||||||
|
|
||||||
return parse_args(settings)
|
|
||||||
end
|
|
||||||
|
|
||||||
function main()
|
|
||||||
|
|
||||||
parsed_args = parse_commandline()
|
|
||||||
if parsed_args["cpus"] ≠ nothing
|
|
||||||
if parsed_args["cpus"] > cpuinfo_physicalcores()
|
|
||||||
warn("Number of specified cores exceeds the physical core cound. Performance will suffer.")
|
|
||||||
end
|
|
||||||
BLAS.set_num_threads(parsed_args["cpus"])
|
|
||||||
end
|
|
||||||
|
|
||||||
N = parsed_args["N"]
|
|
||||||
p = parsed_args["p"]
|
|
||||||
|
|
||||||
if p == 0
|
|
||||||
dirname = "SL$(N)Z"
|
|
||||||
else
|
|
||||||
dirname = "SL$(N)_$p"
|
|
||||||
end
|
|
||||||
|
|
||||||
radius = parsed_args["radius"]
|
|
||||||
tol = parsed_args["tol"]
|
|
||||||
iterations = parsed_args["iterations"]
|
|
||||||
upper_bound = parsed_args["upper-bound"]
|
|
||||||
|
|
||||||
dirname = "$(dirname)_$(upper_bound)_r=$radius"
|
|
||||||
|
|
||||||
logger = PropertyT.setup_logging(dirname)
|
|
||||||
|
|
||||||
info(logger, "Group: $dirname")
|
|
||||||
info(logger, "Iterations: $iterations")
|
|
||||||
info(logger, "Precision: $tol")
|
|
||||||
info(logger, "Upper bound: $upper_bound")
|
|
||||||
|
|
||||||
G, S = SL_generatingset(N, p)
|
|
||||||
info(logger, G)
|
|
||||||
info(logger, "Symmetric generating set of size $(length(S))")
|
|
||||||
Id = one(G)
|
|
||||||
|
|
||||||
solver = SCSSolver(eps=tol, max_iters=iterations, linearsolver=SCS.Direct)
|
|
||||||
|
|
||||||
@time PropertyT.check_property_T(dirname, S, Id, solver, upper_bound, tol, radius)
|
|
||||||
return 0
|
|
||||||
end
|
|
||||||
|
|
||||||
main()
|
|
121
SLNs.jl
121
SLNs.jl
@ -1,121 +0,0 @@
|
|||||||
module SLNs
|
|
||||||
|
|
||||||
using Nemo
|
|
||||||
using Groups
|
|
||||||
|
|
||||||
if VERSION >= v"0.6.0"
|
|
||||||
import Nemo.Generic.perm
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Generating set
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function E(i::Int, j::Int, M::MatSpace, val=one(M.base_ring))
|
|
||||||
@assert i≠j
|
|
||||||
m = one(M)
|
|
||||||
m[i,j] = val
|
|
||||||
return m
|
|
||||||
end
|
|
||||||
|
|
||||||
function SLsize(n,p)
|
|
||||||
result = BigInt(1)
|
|
||||||
for k in 0:n-1
|
|
||||||
result *= p^n - p^k
|
|
||||||
end
|
|
||||||
return div(result, p-1)
|
|
||||||
end
|
|
||||||
|
|
||||||
function generatingset(n::Int, X::Bool=false)
|
|
||||||
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
|
||||||
G = MatrixSpace(ZZ, n, n)
|
|
||||||
if X
|
|
||||||
S = [E(i,j,G,v) for (i,j) in indexing for v in [1, 100]]
|
|
||||||
else
|
|
||||||
S = [E(i,j,G,v) for (i,j) in indexing for v in [1]]
|
|
||||||
end
|
|
||||||
S = vcat(S, [inv(x) for x in S])
|
|
||||||
return G, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
function generatingset(n::Int, p::Int, X::Bool=false)
|
|
||||||
(p > 1 && n > 1) || throw("Both n and p should be positive integers!")
|
|
||||||
info("Size(SL($n,$p)) = $(SLsize(n,p))")
|
|
||||||
F = ResidueRing(ZZ, p)
|
|
||||||
G = MatrixSpace(F, n, n)
|
|
||||||
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
|
||||||
S = [E(i, j, G) for (i,j) in indexing]
|
|
||||||
S = vcat(S, [inv(x) for x in S])
|
|
||||||
return G, unique(S)
|
|
||||||
end
|
|
||||||
|
|
||||||
function generatingset(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
p = parsed_args["p"]
|
|
||||||
X = parsed_args["X"]
|
|
||||||
|
|
||||||
if p == 0
|
|
||||||
return generatingset(N, X)
|
|
||||||
else
|
|
||||||
return generatingset(N, p, X)
|
|
||||||
end
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Action of WreathProductElems on Nemo.MatElem
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function matrix_emb(MM::MatSpace, g::WreathProductElem)
|
|
||||||
parent(g).P.n == MM.cols == MM.rows || throw("No natural embedding of $(parent(g)) in ")
|
|
||||||
powers = [(elt == parent(elt)() ? 0: 1) for elt in g.n.elts]
|
|
||||||
elt = diagm([(-1)^(elt == parent(elt)() ? 0: 1) for elt in g.n.elts])
|
|
||||||
return MM(elt)*MM(Nemo.matrix_repr(g.p)')
|
|
||||||
end
|
|
||||||
|
|
||||||
function (g::WreathProductElem)(A::MatElem)
|
|
||||||
G = matrix_emb(parent(A), g)
|
|
||||||
inv_G = matrix_emb(parent(A), inv(g))
|
|
||||||
return G*A*inv_G
|
|
||||||
end
|
|
||||||
|
|
||||||
function (p::perm)(A::MatElem)
|
|
||||||
length(p.d) == A.r == A.c || throw("Can't act via $p on matrix of size ($(A.r), $(A.c))")
|
|
||||||
R = parent(A)
|
|
||||||
return p*A*inv(p)
|
|
||||||
end
|
|
||||||
|
|
||||||
function autS(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
return WreathProduct(PermutationGroup(2), PermutationGroup(N))
|
|
||||||
# return WreathProduct(FiniteField(2,1, "a")[1], PermutationGroup(N))
|
|
||||||
end
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Misc
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function groupname(parsed_args)
|
|
||||||
N = parsed_args["N"]
|
|
||||||
p = parsed_args["p"]
|
|
||||||
X = parsed_args["X"]
|
|
||||||
|
|
||||||
if p == 0
|
|
||||||
if X
|
|
||||||
name = "oSL$(N)Z⟨X⟩"
|
|
||||||
else
|
|
||||||
name = "oSL$(N)Z"
|
|
||||||
end
|
|
||||||
else
|
|
||||||
name = "oSL$(N)_$p"
|
|
||||||
end
|
|
||||||
|
|
||||||
return name, N
|
|
||||||
end
|
|
||||||
|
|
||||||
end # of module SLNs
|
|
58
SL_orbit.jl
58
SL_orbit.jl
@ -1,58 +0,0 @@
|
|||||||
using ArgParse
|
|
||||||
|
|
||||||
###############################################################################
|
|
||||||
#
|
|
||||||
# Parsing command line
|
|
||||||
#
|
|
||||||
###############################################################################
|
|
||||||
|
|
||||||
function parse_commandline()
|
|
||||||
settings = ArgParseSettings()
|
|
||||||
|
|
||||||
@add_arg_table settings begin
|
|
||||||
"--tol"
|
|
||||||
help = "set numerical tolerance for the SDP solver"
|
|
||||||
arg_type = Float64
|
|
||||||
default = 1e-14
|
|
||||||
"--iterations"
|
|
||||||
help = "set maximal number of iterations for the SDP solver (default: 20000)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 60000
|
|
||||||
"--upper-bound"
|
|
||||||
help = "Set an upper bound for the spectral gap"
|
|
||||||
arg_type = Float64
|
|
||||||
default = Inf
|
|
||||||
"--cpus"
|
|
||||||
help = "Set number of cpus used by solver"
|
|
||||||
arg_type = Int
|
|
||||||
required = false
|
|
||||||
"-N"
|
|
||||||
help = "Consider elementary matrices EL(N)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
"-p"
|
|
||||||
help = "Matrices over field of p-elements (p=0 => over ZZ)"
|
|
||||||
arg_type = Int
|
|
||||||
default = 0
|
|
||||||
"--radius"
|
|
||||||
help = "Radius of ball B_r(e,S) to find solution over"
|
|
||||||
arg_type = Int
|
|
||||||
default = 2
|
|
||||||
"-X"
|
|
||||||
help = "Consider EL(N, ZZ⟨X⟩)"
|
|
||||||
action = :store_true
|
|
||||||
end
|
|
||||||
|
|
||||||
return parse_args(settings)
|
|
||||||
end
|
|
||||||
|
|
||||||
parsed_args = parse_commandline()
|
|
||||||
|
|
||||||
include("CPUselect.jl")
|
|
||||||
|
|
||||||
set_parallel_mthread(parsed_args)
|
|
||||||
|
|
||||||
include("SLNs.jl")
|
|
||||||
include("Orbit.jl")
|
|
||||||
|
|
||||||
main(SLNs, parsed_args)
|
|
56
groups/Allgroups.jl
Normal file
56
groups/Allgroups.jl
Normal file
@ -0,0 +1,56 @@
|
|||||||
|
module PropertyTGroups
|
||||||
|
|
||||||
|
using PropertyT
|
||||||
|
using AbstractAlgebra
|
||||||
|
using Nemo
|
||||||
|
using Groups
|
||||||
|
using GroupRings
|
||||||
|
|
||||||
|
export PropertyTGroup, SymmetrizedGroup, GAPGroup,
|
||||||
|
SpecialLinearGroup,
|
||||||
|
SpecialAutomorphismGroup,
|
||||||
|
HigmanGroup,
|
||||||
|
CapraceGroup,
|
||||||
|
MappingClassGroup
|
||||||
|
|
||||||
|
export PropertyTGroup
|
||||||
|
|
||||||
|
abstract type PropertyTGroup end
|
||||||
|
|
||||||
|
abstract type SymmetrizedGroup <: PropertyTGroup end
|
||||||
|
|
||||||
|
abstract type GAPGroup <: PropertyTGroup end
|
||||||
|
|
||||||
|
function PropertyTGroup(args)
|
||||||
|
if haskey(args, "SL")
|
||||||
|
G = PropertyTGroups.SpecialLinearGroup(args)
|
||||||
|
elseif haskey(args, "SAut")
|
||||||
|
G = PropertyTGroups.SpecialAutomorphismGroup(args)
|
||||||
|
elseif haskey(args, "MCG")
|
||||||
|
G = PropertyTGroups.MappingClassGroup(args)
|
||||||
|
elseif haskey(args, "Higman")
|
||||||
|
G = PropertyTGroups.HigmanGroup(args)
|
||||||
|
elseif haskey(args, "Caprace")
|
||||||
|
G = PropertyTGroups.CapraceGroup(args)
|
||||||
|
else
|
||||||
|
throw("You must provide one of --SL, --SAut, --MCG, --Higman, --Caprace")
|
||||||
|
end
|
||||||
|
return G
|
||||||
|
end
|
||||||
|
|
||||||
|
include("autfreegroup.jl")
|
||||||
|
include("speciallinear.jl")
|
||||||
|
|
||||||
|
Comm(x,y) = x*y*x^-1*y^-1
|
||||||
|
|
||||||
|
function generatingset(G::GAPGroup)
|
||||||
|
S = gens(group(G))
|
||||||
|
return unique([S; inv.(S)])
|
||||||
|
end
|
||||||
|
|
||||||
|
include("mappingclassgroup.jl")
|
||||||
|
include("higman.jl")
|
||||||
|
include("caprace.jl")
|
||||||
|
include("actions.jl")
|
||||||
|
|
||||||
|
end # of module PropertyTGroups
|
92
groups/actions.jl
Normal file
92
groups/actions.jl
Normal file
@ -0,0 +1,92 @@
|
|||||||
|
function (p::perm)(A::GroupRingElem)
|
||||||
|
RG = parent(A)
|
||||||
|
result = zero(RG, eltype(A.coeffs))
|
||||||
|
|
||||||
|
for (idx, c) in enumerate(A.coeffs)
|
||||||
|
if c!= zero(eltype(A.coeffs))
|
||||||
|
result[p(RG.basis[idx])] = c
|
||||||
|
end
|
||||||
|
end
|
||||||
|
return result
|
||||||
|
end
|
||||||
|
|
||||||
|
###############################################################################
|
||||||
|
#
|
||||||
|
# Action of WreathProductElems on Nemo.MatElem
|
||||||
|
#
|
||||||
|
###############################################################################
|
||||||
|
|
||||||
|
function matrix_emb(n::DirectProductGroupElem, p::perm)
|
||||||
|
Id = parent(n.elts[1])()
|
||||||
|
elt = diagm([(-1)^(el == Id ? 0 : 1) for el in n.elts])
|
||||||
|
return elt[:, p.d]
|
||||||
|
end
|
||||||
|
|
||||||
|
function (g::WreathProductElem)(A::MatElem)
|
||||||
|
g_inv = inv(g)
|
||||||
|
G = matrix_emb(g.n, g_inv.p)
|
||||||
|
G_inv = matrix_emb(g_inv.n, g.p)
|
||||||
|
M = parent(A)
|
||||||
|
return M(G)*A*M(G_inv)
|
||||||
|
end
|
||||||
|
|
||||||
|
import Base.*
|
||||||
|
|
||||||
|
doc"""
|
||||||
|
*(x::AbstractAlgebra.MatElem, P::Generic.perm)
|
||||||
|
> Apply the pemutation $P$ to the rows of the matrix $x$ and return the result.
|
||||||
|
"""
|
||||||
|
function *(x::AbstractAlgebra.MatElem, P::Generic.perm)
|
||||||
|
z = similar(x)
|
||||||
|
m = rows(x)
|
||||||
|
n = cols(x)
|
||||||
|
for i = 1:m
|
||||||
|
for j = 1:n
|
||||||
|
z[i, j] = x[i,P[j]]
|
||||||
|
end
|
||||||
|
end
|
||||||
|
return z
|
||||||
|
end
|
||||||
|
|
||||||
|
function (p::perm)(A::MatElem)
|
||||||
|
length(p.d) == A.r == A.c || throw("Can't act via $p on matrix of size ($(A.r), $(A.c))")
|
||||||
|
return p*A*inv(p)
|
||||||
|
end
|
||||||
|
|
||||||
|
###############################################################################
|
||||||
|
#
|
||||||
|
# Action of WreathProductElems on AutGroupElem
|
||||||
|
#
|
||||||
|
###############################################################################
|
||||||
|
|
||||||
|
function AutFG_emb(A::AutGroup, g::WreathProductElem)
|
||||||
|
isa(A.objectGroup, FreeGroup) || throw("Not an Aut(Fₙ)")
|
||||||
|
parent(g).P.n == length(A.objectGroup.gens) || throw("No natural embedding of $(parent(g)) into $A")
|
||||||
|
elt = A()
|
||||||
|
Id = parent(g.n.elts[1])()
|
||||||
|
flips = Groups.AutSymbol[Groups.flip_autsymbol(i) for i in 1:length(g.p.d) if g.n.elts[i] != Id]
|
||||||
|
Groups.r_multiply!(elt, flips, reduced=false)
|
||||||
|
Groups.r_multiply!(elt, [Groups.perm_autsymbol(g.p)])
|
||||||
|
return elt
|
||||||
|
end
|
||||||
|
|
||||||
|
function AutFG_emb(A::AutGroup, p::perm)
|
||||||
|
isa(A.objectGroup, FreeGroup) || throw("Not an Aut(Fₙ)")
|
||||||
|
parent(p).n == length(A.objectGroup.gens) || throw("No natural embedding of $(parent(p)) into $A")
|
||||||
|
return A(Groups.perm_autsymbol(p))
|
||||||
|
end
|
||||||
|
|
||||||
|
function (g::WreathProductElem)(a::Groups.Automorphism)
|
||||||
|
A = parent(a)
|
||||||
|
g = AutFG_emb(A,g)
|
||||||
|
res = A()
|
||||||
|
Groups.r_multiply!(res, g.symbols, reduced=false)
|
||||||
|
Groups.r_multiply!(res, a.symbols, reduced=false)
|
||||||
|
Groups.r_multiply!(res, [inv(s) for s in reverse!(g.symbols)])
|
||||||
|
return res
|
||||||
|
end
|
||||||
|
|
||||||
|
function (p::perm)(a::Groups.Automorphism)
|
||||||
|
g = AutFG_emb(parent(a),p)
|
||||||
|
return g*a*inv(g)
|
||||||
|
end
|
21
groups/autfreegroup.jl
Normal file
21
groups/autfreegroup.jl
Normal file
@ -0,0 +1,21 @@
|
|||||||
|
struct SpecialAutomorphismGroup{N} <: SymmetrizedGroup
|
||||||
|
group::AutGroup
|
||||||
|
end
|
||||||
|
|
||||||
|
function SpecialAutomorphismGroup(args::Dict)
|
||||||
|
N = args["SAut"]
|
||||||
|
return SpecialAutomorphismGroup{N}(AutGroup(FreeGroup(N), special=true))
|
||||||
|
end
|
||||||
|
|
||||||
|
name(G::SpecialAutomorphismGroup{N}) where N = "SAutF$(N)"
|
||||||
|
|
||||||
|
group(G::SpecialAutomorphismGroup) = G.group
|
||||||
|
|
||||||
|
function generatingset(G::SpecialAutomorphismGroup)
|
||||||
|
S = gens(group(G));
|
||||||
|
return unique([S; inv.(S)])
|
||||||
|
end
|
||||||
|
|
||||||
|
function autS(G::SpecialAutomorphismGroup{N}) where N
|
||||||
|
return WreathProduct(PermutationGroup(2), PermutationGroup(N))
|
||||||
|
end
|
35
groups/caprace.jl
Normal file
35
groups/caprace.jl
Normal file
@ -0,0 +1,35 @@
|
|||||||
|
struct CapraceGroup <: GAPGroup end
|
||||||
|
|
||||||
|
name(G::CapraceGroup) = "CapraceGroup"
|
||||||
|
|
||||||
|
function group(G::CapraceGroup)
|
||||||
|
|
||||||
|
caprace_group = Groups.FPGroup(["x","y","z","t","r"])
|
||||||
|
|
||||||
|
x,y,z,t,r = gens(caprace_group)
|
||||||
|
|
||||||
|
relations = [
|
||||||
|
x^7,
|
||||||
|
y^7,
|
||||||
|
t^2,
|
||||||
|
r^73,
|
||||||
|
t*r*t*r,
|
||||||
|
Comm(x,y)*z^-1,
|
||||||
|
Comm(x,z),
|
||||||
|
Comm(y,z),
|
||||||
|
Comm(x^2*y*z^-1, t),
|
||||||
|
Comm(x*y*z^3, t*r),
|
||||||
|
Comm(x^3*y*z^2, t*r^17),
|
||||||
|
Comm(x, t*r^-34),
|
||||||
|
Comm(y, t*r^-32),
|
||||||
|
Comm(z, t*r^-29),
|
||||||
|
Comm(x^-2*y*z, t*r^-25),
|
||||||
|
Comm(x^-1*y*z^-3, t*r^-19),
|
||||||
|
Comm(x^-3*y*z^-2, t*r^-11)
|
||||||
|
];
|
||||||
|
|
||||||
|
relations = [relations; [inv(rel) for rel in relations]]
|
||||||
|
|
||||||
|
Groups.add_rels!(caprace_group, Dict(rel => caprace_group() for rel in relations))
|
||||||
|
return caprace_group
|
||||||
|
end
|
22
groups/higman.jl
Normal file
22
groups/higman.jl
Normal file
@ -0,0 +1,22 @@
|
|||||||
|
struct HigmanGroup <: GAPGroup end
|
||||||
|
|
||||||
|
name(G::HigmanGroup) = "HigmanGroup"
|
||||||
|
|
||||||
|
function group(G::HigmanGroup)
|
||||||
|
|
||||||
|
higman_group = Groups.FPGroup(["a","b","c","d"]);
|
||||||
|
|
||||||
|
a,b,c,d = gens(higman_group)
|
||||||
|
|
||||||
|
relations = [
|
||||||
|
b*Comm(b,a),
|
||||||
|
c*Comm(c,b),
|
||||||
|
d*Comm(d,c),
|
||||||
|
a*Comm(a,d)
|
||||||
|
];
|
||||||
|
|
||||||
|
relations = [relations; [inv(rel) for rel in relations]]
|
||||||
|
|
||||||
|
Groups.add_rels!(higman_group, Dict(rel => higman_group() for rel in relations))
|
||||||
|
return higman_group
|
||||||
|
end
|
83
groups/mappingclassgroup.jl
Normal file
83
groups/mappingclassgroup.jl
Normal file
@ -0,0 +1,83 @@
|
|||||||
|
struct MappingClassGroup{N} <: GAPGroup end
|
||||||
|
|
||||||
|
MappingClassGroup(args::Dict) = MappingClassGroup{args["MCG"]}()
|
||||||
|
|
||||||
|
name(G::MappingClassGroup{N}) where N = "MCG(N)"
|
||||||
|
|
||||||
|
function group(G::MappingClassGroup{N}) where N
|
||||||
|
|
||||||
|
if N < 2
|
||||||
|
throw("Genus must be at least 2!")
|
||||||
|
elseif N == 2
|
||||||
|
MCGroup = Groups.FPGroup(["a1","a2","a3","a4","a5"]);
|
||||||
|
S = gens(MCGroup)
|
||||||
|
|
||||||
|
n = length(S)
|
||||||
|
A = prod(reverse(S))*prod(S)
|
||||||
|
|
||||||
|
relations = [
|
||||||
|
[Comm(S[i], S[j]) for i in 1:n for j in 1:n if abs(i-j) > 1]...,
|
||||||
|
[S[i]*S[i+1]*S[i]*inv(S[i+1]*S[i]*S[i+1]) for i in 1:G.n-1]...,
|
||||||
|
(S[1]*S[2]*S[3])^4*inv(S[5])^2,
|
||||||
|
Comm(A, S[1]),
|
||||||
|
A^2
|
||||||
|
]
|
||||||
|
|
||||||
|
relations = [relations; [inv(rel) for rel in relations]]
|
||||||
|
Groups.add_rels!(MCGroup, Dict(rel => MCGroup() for rel in relations))
|
||||||
|
return MCGroup
|
||||||
|
|
||||||
|
else
|
||||||
|
MCGroup = Groups.FPGroup(["a$i" for i in 0:2N])
|
||||||
|
S = gens(MCGroup)
|
||||||
|
|
||||||
|
a0 = S[1]
|
||||||
|
A = S[2:end]
|
||||||
|
k = length(A)
|
||||||
|
|
||||||
|
relations = [
|
||||||
|
[Comm(A[i], A[j]) for i in 1:k for j in 1:k if abs(i-j) > 1]...,
|
||||||
|
[Comm(a0, A[i]) for i in 1:k if i != 4]...,
|
||||||
|
[A[i]*A[(i+1)]*A[i]*inv(A[i+1]*A[i]*A[i+1]) for i in 1:k-1]...,
|
||||||
|
A[4]*a0*A[4]*inv(a0*A[4]*a0)
|
||||||
|
]
|
||||||
|
|
||||||
|
# 3-chain relation
|
||||||
|
c = prod(reverse(A[1:4]))*prod(A[1:4])
|
||||||
|
b0 = c*a0*inv(c)
|
||||||
|
push!(relations, (A[1]*A[2]*A[3])^4*inv(a0*b0))
|
||||||
|
|
||||||
|
# Lantern relation
|
||||||
|
b1 = inv(A[4]*A[5]*A[3]*A[4])*a0*(A[4]*A[5]*A[3]*A[4])
|
||||||
|
b2 = inv(A[2]*A[3]*A[1]*A[2])*b1*(A[2]*A[3]*A[1]*A[2])
|
||||||
|
u = inv(A[6]*A[5])*b1*(A[6]*A[5])
|
||||||
|
x = prod(reverse(A[2:6]))*u*prod(inv.(A[1:4]))
|
||||||
|
b3 = x*a0*inv(x)
|
||||||
|
push!(relations, a0*b2*b1*inv(A[1]*A[3]*A[5]*b3))
|
||||||
|
|
||||||
|
# Hyperelliptic relation
|
||||||
|
X = prod(reverse(A))*prod(A)
|
||||||
|
|
||||||
|
function n(i::Int, b=b0)
|
||||||
|
if i == 1
|
||||||
|
return A[1]
|
||||||
|
elseif i == 2
|
||||||
|
return b
|
||||||
|
else
|
||||||
|
return w(i-2)*n(i-2)*w(i-2)
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
function w(i::Int)
|
||||||
|
(A[2i+4]*A[2i+3]*A[2i+2]* n(i+1))*(A[2i+1]*A[2i] *A[2i+2]*A[2i+1])*
|
||||||
|
(A[2i+3]*A[2i+2]*A[2i+4]*A[2i+3])*( n(i+1)*A[2i+2]*A[2i+1]*A[2i] )
|
||||||
|
end
|
||||||
|
|
||||||
|
# push!(relations, X*n(N)*inv(n(N)*X))
|
||||||
|
|
||||||
|
relations = [relations; [inv(rel) for rel in relations]]
|
||||||
|
Groups.add_rels!(MCGroup, Dict(rel => MCGroup() for rel in relations))
|
||||||
|
|
||||||
|
return MCGroup
|
||||||
|
end
|
||||||
|
end
|
62
groups/speciallinear.jl
Normal file
62
groups/speciallinear.jl
Normal file
@ -0,0 +1,62 @@
|
|||||||
|
struct SpecialLinearGroup{N} <: SymmetrizedGroup
|
||||||
|
group::AbstractAlgebra.Group
|
||||||
|
p::Int
|
||||||
|
X::Bool
|
||||||
|
end
|
||||||
|
|
||||||
|
function SpecialLinearGroup(args::Dict)
|
||||||
|
N = args["SL"]
|
||||||
|
p = args["p"]
|
||||||
|
X = args["X"]
|
||||||
|
|
||||||
|
if p == 0
|
||||||
|
G = MatrixSpace(Nemo.ZZ, N, N)
|
||||||
|
else
|
||||||
|
R = Nemo.NmodRing(UInt(p))
|
||||||
|
G = MatrixSpace(R, N, N)
|
||||||
|
end
|
||||||
|
return SpecialLinearGroup{N}(G, p, X)
|
||||||
|
end
|
||||||
|
|
||||||
|
function name(G::SpecialLinearGroup{N}) where N
|
||||||
|
if G.p == 0
|
||||||
|
R = (G.X ? "Z[x]" : "Z")
|
||||||
|
else
|
||||||
|
R = "F$(G.p)"
|
||||||
|
end
|
||||||
|
return SL($(G.N),$R)
|
||||||
|
end
|
||||||
|
|
||||||
|
group(G::SpecialLinearGroup) = G.group
|
||||||
|
|
||||||
|
function generatingset(G::SpecialLinearGroup{N}) where N
|
||||||
|
G.p > 0 && G.X && throw("SL(n, F_p[x]) not implemented")
|
||||||
|
SL = group(G)
|
||||||
|
return generatingset(SL, G.X)
|
||||||
|
end
|
||||||
|
|
||||||
|
# r is the injectivity radius of
|
||||||
|
# SL(n, Z[X]) -> SL(n, Z) induced by X -> 100
|
||||||
|
|
||||||
|
function generatingset(SL::MatSpace, X::Bool=false, r=5)
|
||||||
|
n = SL.cols
|
||||||
|
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
||||||
|
|
||||||
|
if !X
|
||||||
|
S = [E(idx[1],idx[2],SL) for idx in indexing]
|
||||||
|
else
|
||||||
|
S = [E(i,j,SL,v) for (i,j) in indexing for v in [1, 100*r]]
|
||||||
|
end
|
||||||
|
return unique([S; inv.(S)])
|
||||||
|
end
|
||||||
|
|
||||||
|
function E(i::Int, j::Int, M::MatSpace, val=one(M.base_ring))
|
||||||
|
@assert i≠j
|
||||||
|
m = one(M)
|
||||||
|
m[i,j] = val
|
||||||
|
return m
|
||||||
|
end
|
||||||
|
|
||||||
|
function autS(G::SpecialLinearGroup{N}) where N
|
||||||
|
return WreathProduct(PermutationGroup(2), PermutationGroup(N))
|
||||||
|
end
|
58
logging.jl
Normal file
58
logging.jl
Normal file
@ -0,0 +1,58 @@
|
|||||||
|
using Memento
|
||||||
|
|
||||||
|
function setup_logging(filename::String, handlername::Symbol=:log)
|
||||||
|
isdir(dirname(filename)) || mkdir(dirname(filename))
|
||||||
|
logger = Memento.config!("info", fmt="{date}| {msg}")
|
||||||
|
handler = DefaultHandler(filename, DefaultFormatter("{date}| {msg}"))
|
||||||
|
logger.handlers[String(handlername)] = handler
|
||||||
|
return logger
|
||||||
|
end
|
||||||
|
|
||||||
|
macro logtime(logger, ex)
|
||||||
|
quote
|
||||||
|
local stats = Base.gc_num()
|
||||||
|
local elapsedtime = Base.time_ns()
|
||||||
|
local val = $(esc(ex))
|
||||||
|
elapsedtime = Base.time_ns() - elapsedtime
|
||||||
|
local diff = Base.GC_Diff(Base.gc_num(), stats)
|
||||||
|
local ts = time_string(elapsedtime,
|
||||||
|
diff.allocd,
|
||||||
|
diff.total_time,
|
||||||
|
Base.gc_alloc_count(diff)
|
||||||
|
)
|
||||||
|
$(esc(info))($(esc(logger)), ts)
|
||||||
|
val
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
function time_string(elapsedtime, bytes, gctime, allocs)
|
||||||
|
str = @sprintf("%10.6f seconds", elapsedtime/1e9)
|
||||||
|
if bytes != 0 || allocs != 0
|
||||||
|
bytes, mb = Base.prettyprint_getunits(bytes, length(Base._mem_units), Int64(1024))
|
||||||
|
allocs, ma = Base.prettyprint_getunits(allocs, length(Base._cnt_units), Int64(1000))
|
||||||
|
if ma == 1
|
||||||
|
str*= @sprintf(" (%d%s allocation%s: ", allocs, Base._cnt_units[ma], allocs==1 ? "" : "s")
|
||||||
|
else
|
||||||
|
str*= @sprintf(" (%.2f%s allocations: ", allocs, Base._cnt_units[ma])
|
||||||
|
end
|
||||||
|
if mb == 1
|
||||||
|
str*= @sprintf("%d %s%s", bytes, Base._mem_units[mb], bytes==1 ? "" : "s")
|
||||||
|
else
|
||||||
|
str*= @sprintf("%.3f %s", bytes, Base._mem_units[mb])
|
||||||
|
end
|
||||||
|
if gctime > 0
|
||||||
|
str*= @sprintf(", %.2f%% gc time", 100*gctime/elapsedtime)
|
||||||
|
end
|
||||||
|
str*=")"
|
||||||
|
elseif gctime > 0
|
||||||
|
str*= @sprintf(", %.2f%% gc time", 100*gctime/elapsedtime)
|
||||||
|
end
|
||||||
|
return str
|
||||||
|
end
|
||||||
|
|
||||||
|
import Base: info, @time
|
||||||
|
|
||||||
|
Base.info(x) = info(getlogger(), x)
|
||||||
|
macro time(x)
|
||||||
|
return :(@logtime(getlogger(Main), $(esc(x))))
|
||||||
|
end
|
61
main.jl
Normal file
61
main.jl
Normal file
@ -0,0 +1,61 @@
|
|||||||
|
using PropertyT
|
||||||
|
|
||||||
|
include("FPGroups_GAP.jl")
|
||||||
|
|
||||||
|
include("groups/Allgroups.jl")
|
||||||
|
using PropertyTGroups
|
||||||
|
|
||||||
|
import PropertyT.Settings
|
||||||
|
|
||||||
|
function summarize(sett::PropertyT.Settings)
|
||||||
|
info("Threads: $(Threads.nthreads())")
|
||||||
|
info("Workers: $(workers())")
|
||||||
|
info("GroupDir: $(PropertyT.prepath(sett))")
|
||||||
|
info(string(sett.G))
|
||||||
|
info("with generating set of size $(length(sett.S))")
|
||||||
|
|
||||||
|
info("Radius: $(sett.radius)")
|
||||||
|
info("Precision: $(sett.tol)")
|
||||||
|
info("Upper bound: $(sett.upper_bound)")
|
||||||
|
info("Solver: $(sett.solver)")
|
||||||
|
end
|
||||||
|
|
||||||
|
function Settings(Gr::PropertyTGroup, args, solver)
|
||||||
|
r = get(args, "radius", 2)
|
||||||
|
gr_name = PropertyTGroups.name(Gr)*"_r$r"
|
||||||
|
G = PropertyTGroups.group(Gr)
|
||||||
|
S = PropertyTGroups.generatingset(Gr)
|
||||||
|
|
||||||
|
sol = solver
|
||||||
|
ub = get(args,"upper-bound", Inf)
|
||||||
|
tol = get(args,"tol", 1e-10)
|
||||||
|
ws = get(args, "warmstart", false)
|
||||||
|
|
||||||
|
if get(args, "nosymmetry", false)
|
||||||
|
return PropertyT.Settings(gr_name, G, S, r, sol, ub, tol, ws)
|
||||||
|
else
|
||||||
|
autS = PropertyTGroups.autS(Gr)
|
||||||
|
return PropertyT.Settings(gr_name, G, S, r, sol, ub, tol, ws, autS)
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
function main(::PropertyTGroup, sett::PropertyT.Settings)
|
||||||
|
isdir(PropertyT.fullpath(sett)) || mkpath(PropertyT.fullpath(sett))
|
||||||
|
|
||||||
|
summarize(sett)
|
||||||
|
|
||||||
|
return PropertyT.check_property_T(sett)
|
||||||
|
end
|
||||||
|
|
||||||
|
function main(::GAPGroup, sett::PropertyT.Settings)
|
||||||
|
isdir(PropertyT.fullpath(sett)) || mkpath(PropertyT.fullpath(sett))
|
||||||
|
|
||||||
|
summarize(sett)
|
||||||
|
|
||||||
|
S = [s for s in sett.S if s.symbols[1].pow == 1]
|
||||||
|
relations = [k*inv(v) for (k,v) in sett.G.rels]
|
||||||
|
|
||||||
|
prepare_pm_delta(PropertyT.prepath(sett), GAP_groupcode(S, relations), sett.radius)
|
||||||
|
|
||||||
|
return PropertyT.check_property_T(sett)
|
||||||
|
end
|
197
positivity/check_positivity.jl
Normal file
197
positivity/check_positivity.jl
Normal file
@ -0,0 +1,197 @@
|
|||||||
|
using AbstractAlgebra
|
||||||
|
using Groups
|
||||||
|
using GroupRings
|
||||||
|
using PropertyT
|
||||||
|
|
||||||
|
using SCS
|
||||||
|
solver(tol, iterations) =
|
||||||
|
SCSSolver(linearsolver=SCS.Direct,
|
||||||
|
eps=tol, max_iters=iterations,
|
||||||
|
alpha=1.95, acceleration_lookback=1)
|
||||||
|
|
||||||
|
include("../main.jl")
|
||||||
|
|
||||||
|
using PropertyTGroups
|
||||||
|
|
||||||
|
args = Dict("SAut" => 5, "upper-bound" => 50.0, "radius" => 2, "nosymmetry"=>false, "tol"=>1e-12, "iterations" =>200000, "warmstart" => true)
|
||||||
|
|
||||||
|
Gr = PropertyTGroups.PropertyTGroup(args)
|
||||||
|
sett = PropertyT.Settings(Gr, args,
|
||||||
|
solver(args["tol"], args["iterations"]))
|
||||||
|
|
||||||
|
@show sett
|
||||||
|
|
||||||
|
fullpath = PropertyT.fullpath(sett)
|
||||||
|
isdir(fullpath) || mkpath(fullpath)
|
||||||
|
# setup_logging(PropertyT.filename(fullpath, :fulllog), :fulllog)
|
||||||
|
|
||||||
|
function small_generating_set(RG::GroupRing{AutGroup{N}}, n) where N
|
||||||
|
indexing = [(i,j) for i in 1:n for j in 1:n if i≠j]
|
||||||
|
|
||||||
|
rmuls = [Groups.rmul_autsymbol(i,j) for (i,j) in indexing]
|
||||||
|
lmuls = [Groups.lmul_autsymbol(i,j) for (i,j) in indexing]
|
||||||
|
gen_set = RG.group.([rmuls; lmuls])
|
||||||
|
|
||||||
|
return [gen_set; inv.(gen_set)]
|
||||||
|
end
|
||||||
|
|
||||||
|
function computeX(RG::GroupRing{AutGroup{N}}) where N
|
||||||
|
Tn = small_generating_set(RG, N-1)
|
||||||
|
|
||||||
|
ℤ = Int64
|
||||||
|
Δn = length(Tn)*one(RG, ℤ) - RG(Tn, ℤ);
|
||||||
|
|
||||||
|
Alt_N = [g for g in elements(PermutationGroup(N)) if parity(g) == 0]
|
||||||
|
|
||||||
|
@time X = sum(σ(Δn)*sum(τ(Δn) for τ ∈ Alt_N if τ ≠ σ) for σ in Alt_N);
|
||||||
|
return X
|
||||||
|
end
|
||||||
|
|
||||||
|
function Sq(RG::GroupRing{AutGroup{N}}) where N
|
||||||
|
T2 = small_generating_set(RG, 2)
|
||||||
|
ℤ = Int64
|
||||||
|
Δ₂ = length(T2)*one(RG, ℤ) - RG(T2, ℤ);
|
||||||
|
|
||||||
|
Alt_N = [g for g in elements(PermutationGroup(N)) if parity(g) == 0]
|
||||||
|
elt = sum(σ(Δ₂)^2 for σ in Alt_N)
|
||||||
|
return elt
|
||||||
|
end
|
||||||
|
|
||||||
|
function Adj(RG::GroupRing{AutGroup{N}}) where N
|
||||||
|
T2 = small_generating_set(RG, 2)
|
||||||
|
|
||||||
|
ℤ = Int64
|
||||||
|
Δ₂ = length(T2)*one(RG, ℤ) - RG(T2, ℤ);
|
||||||
|
|
||||||
|
Alt_N = [g for g in elements(PermutationGroup(N)) if parity(g) == 0]
|
||||||
|
|
||||||
|
adj(σ::perm, τ::perm, i=1, j=2) = Set([σ[i], σ[j]]) ∩ Set([τ[i], τ[j]])
|
||||||
|
adj(σ::perm) = [τ for τ in Alt_N if length(adj(σ, τ)) == 1]
|
||||||
|
|
||||||
|
@time elt = sum(σ(Δ₂)*sum(τ(Δ₂) for τ in adj(σ)) for σ in Alt_N);
|
||||||
|
# return RG(elt.coeffs÷factorial(N-2)^2)
|
||||||
|
return elt
|
||||||
|
end
|
||||||
|
|
||||||
|
function Op(RG::GroupRing{AutGroup{N}}) where N
|
||||||
|
T2 = small_generating_set(RG, 2)
|
||||||
|
|
||||||
|
ℤ = Int64
|
||||||
|
Δ₂ = length(T2)*one(RG, ℤ) - RG(T2, ℤ);
|
||||||
|
|
||||||
|
Alt_N = [g for g in elements(PermutationGroup(N)) if parity(g) == 0]
|
||||||
|
|
||||||
|
adj(σ::perm, τ::perm, i=1, j=2) = Set([σ[i], σ[j]]) ∩ Set([τ[i], τ[j]])
|
||||||
|
adj(σ::perm) = [τ for τ in Alt_N if length(adj(σ, τ)) == 0]
|
||||||
|
|
||||||
|
@time elt = sum(σ(Δ₂)*sum(τ(Δ₂) for τ in adj(σ)) for σ in Alt_N);
|
||||||
|
# return RG(elt.coeffs÷factorial(N-2)^2)
|
||||||
|
return elt
|
||||||
|
end
|
||||||
|
|
||||||
|
const ELT_FILE = joinpath(dirname(PropertyT.filename(sett, :Δ)), "SqAdjOp_coeffs.jld")
|
||||||
|
const WARMSTART_FILE = PropertyT.filename(sett, :warmstart)
|
||||||
|
|
||||||
|
if isfile(PropertyT.filename(sett,:Δ)) && isfile(ELT_FILE) &&
|
||||||
|
isfile(PropertyT.filename(sett, :OrbitData))
|
||||||
|
# cached
|
||||||
|
Δ = PropertyT.loadGRElem(PropertyT.filename(sett,:Δ), sett.G)
|
||||||
|
RG = parent(Δ)
|
||||||
|
orbit_data = load(PropertyT.filename(sett, :OrbitData), "OrbitData")
|
||||||
|
sq_c, adj_c, op_c = load(ELT_FILE, "Sq", "Adj", "Op")
|
||||||
|
# elt = ELT_FILE, sett.G)
|
||||||
|
sq = GroupRingElem(sq_c, RG)
|
||||||
|
adj = GroupRingElem(adj_c, RG)
|
||||||
|
op = GroupRingElem(op_c, RG);
|
||||||
|
else
|
||||||
|
info("Compute Laplacian")
|
||||||
|
Δ = PropertyT.Laplacian(sett.S, sett.radius)
|
||||||
|
RG = parent(Δ)
|
||||||
|
|
||||||
|
info("Compute Sq, Adj, Op")
|
||||||
|
@time sq, adj, op = Sq(RG), Adj(RG), Op(RG)
|
||||||
|
|
||||||
|
PropertyT.saveGRElem(PropertyT.filename(sett, :Δ), Δ)
|
||||||
|
save(ELT_FILE, "Sq", sq.coeffs, "Adj", adj.coeffs, "Op", op.coeffs)
|
||||||
|
|
||||||
|
info("Compute OrbitData")
|
||||||
|
if !isfile(PropertyT.filename(sett, :OrbitData))
|
||||||
|
orbit_data = PropertyT.OrbitData(parent(Y), sett.autS)
|
||||||
|
save(PropertyT.filename(sett, :OrbitData), "OrbitData", orbit_data)
|
||||||
|
else
|
||||||
|
orbit_data = load(PropertyT.filename(sett, :OrbitData), "OrbitData")
|
||||||
|
end
|
||||||
|
end;
|
||||||
|
|
||||||
|
orbit_data = PropertyT.decimate(orbit_data);
|
||||||
|
|
||||||
|
elt = adj+2op;
|
||||||
|
|
||||||
|
const SOLUTION_FILE = PropertyT.filename(sett, :solution)
|
||||||
|
|
||||||
|
if !isfile(SOLUTION_FILE)
|
||||||
|
|
||||||
|
SDP_problem, varλ, varP = PropertyT.SOS_problem(elt, Δ, orbit_data; upper_bound=sett.upper_bound)
|
||||||
|
|
||||||
|
begin
|
||||||
|
using SCS
|
||||||
|
scs_solver = SCS.SCSSolver(linearsolver=SCS.Direct,
|
||||||
|
eps=sett.tol,
|
||||||
|
max_iters=args["iterations"],
|
||||||
|
alpha=1.95,
|
||||||
|
acceleration_lookback=1)
|
||||||
|
|
||||||
|
JuMP.setsolver(SDP_problem, scs_solver)
|
||||||
|
end
|
||||||
|
|
||||||
|
λ = Ps = nothing
|
||||||
|
ws = PropertyT.warmstart(sett)
|
||||||
|
|
||||||
|
# using ProgressMeter
|
||||||
|
|
||||||
|
# @showprogress "Running SDP optimization step... " for i in 1:args["repetitions"]
|
||||||
|
while true
|
||||||
|
λ, Ps, ws = PropertyT.solve(PropertyT.filename(sett, :solverlog),
|
||||||
|
SDP_problem, varλ, varP, ws);
|
||||||
|
|
||||||
|
if all((!isnan).(ws[1]))
|
||||||
|
save(WARMSTART_FILE, "warmstart", ws, "λ", λ, "Ps", Ps)
|
||||||
|
save(WARMSTART_FILE[1:end-4]*"_$(now()).jld", "warmstart", ws, "λ", λ, "Ps", Ps)
|
||||||
|
else
|
||||||
|
warn("No valid solution was saved!")
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
info("Reconstructing P...")
|
||||||
|
@time P = PropertyT.reconstruct(Ps, orbit_data);
|
||||||
|
save(SOLUTION_FILE, "λ", λ, "P", P)
|
||||||
|
end
|
||||||
|
|
||||||
|
P, λ = load(SOLUTION_FILE, "P", "λ")
|
||||||
|
@show λ;
|
||||||
|
|
||||||
|
@time const Q = real(sqrtm(P));
|
||||||
|
|
||||||
|
function SOS_residual(eoi::GroupRingElem, Q::Matrix)
|
||||||
|
RG = parent(eoi)
|
||||||
|
@time sos = PropertyT.compute_SOS(RG, Q);
|
||||||
|
return eoi - sos
|
||||||
|
end
|
||||||
|
|
||||||
|
info("Floating Point arithmetic:")
|
||||||
|
EOI = elt - λ*Δ
|
||||||
|
b = SOS_residual(EOI, Q)
|
||||||
|
@show norm(b, 1);
|
||||||
|
|
||||||
|
info("Interval arithmetic:")
|
||||||
|
using IntervalArithmetic
|
||||||
|
Qint = PropertyT.augIdproj(Q);
|
||||||
|
@assert all([zero(eltype(Q)) in sum(view(Qint, :, i)) for i in 1:size(Qint, 2)])
|
||||||
|
|
||||||
|
EOI_int = elt - @interval(λ)*Δ;
|
||||||
|
Q_int = PropertyT.augIdproj(Q);
|
||||||
|
@assert all([zero(eltype(Q)) in sum(view(Q_int, :, i)) for i in 1:size(Q_int, 2)])
|
||||||
|
b_int = SOS_residual(EOI_int, Q_int)
|
||||||
|
@show norm(b_int, 1);
|
||||||
|
|
||||||
|
info("λ is certified to be > ", (@interval(λ) - 2^2*norm(b_int,1)).lo)
|
108
run.jl
Normal file
108
run.jl
Normal file
@ -0,0 +1,108 @@
|
|||||||
|
using ArgParse
|
||||||
|
|
||||||
|
###############################################################################
|
||||||
|
#
|
||||||
|
# Parsing command line
|
||||||
|
#
|
||||||
|
###############################################################################
|
||||||
|
|
||||||
|
function parse_commandline()
|
||||||
|
settings = ArgParseSettings()
|
||||||
|
|
||||||
|
@add_arg_table settings begin
|
||||||
|
"--tol"
|
||||||
|
help = "set numerical tolerance for the SDP solver"
|
||||||
|
arg_type = Float64
|
||||||
|
default = 1e-6
|
||||||
|
"--iterations"
|
||||||
|
help = "set maximal number of iterations for the SDP solver"
|
||||||
|
arg_type = Int
|
||||||
|
default = 50000
|
||||||
|
"--upper-bound"
|
||||||
|
help = "Set an upper bound for the spectral gap"
|
||||||
|
arg_type = Float64
|
||||||
|
default = Inf
|
||||||
|
"--cpus"
|
||||||
|
help = "Set number of cpus used by solver"
|
||||||
|
arg_type = Int
|
||||||
|
required = false
|
||||||
|
"--radius"
|
||||||
|
help = "Radius of ball B_r(e,S) to find solution over"
|
||||||
|
arg_type = Int
|
||||||
|
default = 2
|
||||||
|
"--warmstart"
|
||||||
|
help = "Use warmstart.jld as the initial guess for SCS"
|
||||||
|
action = :store_true
|
||||||
|
"--nosymmetry"
|
||||||
|
help = "Don't use symmetries of the Laplacian"
|
||||||
|
action = :store_true
|
||||||
|
|
||||||
|
"--SL "
|
||||||
|
help = "GROUP: the group generated by elementary matrices of size n by n"
|
||||||
|
arg_type = Int
|
||||||
|
required = false
|
||||||
|
"-p"
|
||||||
|
help = "Matrices over field of p-elements (p=0 => over ZZ) [only with --SL]"
|
||||||
|
arg_type = Int
|
||||||
|
default = 0
|
||||||
|
"-X"
|
||||||
|
help = "Consider EL(N, ZZ⟨X⟩) [only with --SL]"
|
||||||
|
action = :store_true
|
||||||
|
|
||||||
|
"--SAut"
|
||||||
|
help = "GROUP: the automorphisms group of the free group on N generators"
|
||||||
|
arg_type = Int
|
||||||
|
required = false
|
||||||
|
|
||||||
|
"--MCG"
|
||||||
|
help = "GROUP: mapping class group of surface of genus N"
|
||||||
|
arg_type = Int
|
||||||
|
required = false
|
||||||
|
|
||||||
|
"--Higman"
|
||||||
|
help = "GROUP: the Higman Group"
|
||||||
|
action = :store_true
|
||||||
|
|
||||||
|
"--Caprace"
|
||||||
|
help = "GROUP: for Caprace Group"
|
||||||
|
action = :store_true
|
||||||
|
end
|
||||||
|
return parse_args(settings)
|
||||||
|
end
|
||||||
|
|
||||||
|
const PARSEDARGS = parse_commandline()
|
||||||
|
|
||||||
|
set_parallel_mthread(PARSEDARGS, workers=false)
|
||||||
|
|
||||||
|
include("CPUselect.jl")
|
||||||
|
include("logging.jl")
|
||||||
|
include("main.jl")
|
||||||
|
|
||||||
|
using SCS.SCSSolver
|
||||||
|
# using Mosek
|
||||||
|
# using CSDP
|
||||||
|
# using SDPA
|
||||||
|
|
||||||
|
solver(tol, iterations) =
|
||||||
|
SCSSolver(linearsolver=SCS.Direct,
|
||||||
|
eps=tol, max_iters=iterations,
|
||||||
|
alpha=1.95, acceleration_lookback=1)
|
||||||
|
|
||||||
|
# Mosek.MosekSolver(
|
||||||
|
# MSK_DPAR_INTPNT_CO_TOL_REL_GAP=tol,
|
||||||
|
# MSK_IPAR_INTPNT_MAX_ITERATIONS=iterations,
|
||||||
|
# QUIET=false)
|
||||||
|
|
||||||
|
# CSDP.CSDPSolver(axtol=tol, atytol=tol, objtol=tol, minstepp=tol*10.0^-1, minstepd=tol*10.0^-1)
|
||||||
|
|
||||||
|
# SDPA.SDPASolver(epsilonStar=tol, epsilonDash=tol)
|
||||||
|
|
||||||
|
const Gr = PropertyTGroups.PropertyTGroup(PARSEDARGS)
|
||||||
|
const sett = PropertyT.Settings(Gr, PARSEDARGS,
|
||||||
|
solver(PARSEDARGS["tol"], PARSEDARGS["iterations"]))
|
||||||
|
|
||||||
|
fullpath = PropertyT.fullpath(sett)
|
||||||
|
isdir(fullpath) || mkpath(fullpath)
|
||||||
|
setup_logging(PropertyT.filename(fullpath, :fulllog), :fulllog)
|
||||||
|
|
||||||
|
main(Gr, sett)
|
222
runtests.jl
Normal file
222
runtests.jl
Normal file
@ -0,0 +1,222 @@
|
|||||||
|
using Base.Test
|
||||||
|
|
||||||
|
include("main.jl")
|
||||||
|
|
||||||
|
testdir = "tests_"*string(now())
|
||||||
|
mkdir(testdir)
|
||||||
|
include("logging.jl")
|
||||||
|
logger=setup_logging(joinpath(testdir, "tests.log"))
|
||||||
|
info(testdir)
|
||||||
|
|
||||||
|
cd(testdir)
|
||||||
|
|
||||||
|
# groupname = name(G)
|
||||||
|
# ub = PARSEDARGS["upper-bound"]
|
||||||
|
#
|
||||||
|
# fullpath = joinpath(groupname, string(ub))
|
||||||
|
# isdir(fullpath) || mkpath(fullpath)
|
||||||
|
|
||||||
|
separator(n=60) = info("\n"*("\n"*"="^n*"\n"^3)*"\n")
|
||||||
|
|
||||||
|
|
||||||
|
function SL_tests(args)
|
||||||
|
|
||||||
|
|
||||||
|
args["SL"] = 2
|
||||||
|
args["p"] = 3
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == true
|
||||||
|
separator()
|
||||||
|
|
||||||
|
let args = args
|
||||||
|
args["SL"] = 2
|
||||||
|
args["p"] = 5
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
args["warmstart"] = true
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
args["upper-bound"] = 0.1
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == true
|
||||||
|
separator()
|
||||||
|
end
|
||||||
|
|
||||||
|
args["SL"] = 2
|
||||||
|
args["p"] = 7
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
args["SL"] = 3
|
||||||
|
args["p"] = 7
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == true
|
||||||
|
separator()
|
||||||
|
|
||||||
|
# begin
|
||||||
|
# args["iterations"] = 25000
|
||||||
|
# args["N"] = 3
|
||||||
|
# args["p"] = 0
|
||||||
|
# args["upper-bound"] = Inf
|
||||||
|
#
|
||||||
|
# G = PropertyTGroups.SpecialLinearGroup(args)
|
||||||
|
# @test main(G) == false
|
||||||
|
# separator()
|
||||||
|
#
|
||||||
|
# args["warmstart"] = false
|
||||||
|
# args["upper-bound"] = 0.27
|
||||||
|
# G = PropertyTGroups.SpecialLinearGroup(args)
|
||||||
|
# @test main(G) == false
|
||||||
|
# separator()
|
||||||
|
#
|
||||||
|
# args["warmstart"] = true
|
||||||
|
# G = PropertyTGroups.SpecialLinearGroup(args)
|
||||||
|
# @test main(G) == true
|
||||||
|
# separator()
|
||||||
|
# end
|
||||||
|
|
||||||
|
return 0
|
||||||
|
end
|
||||||
|
|
||||||
|
function SAut_tests(args)
|
||||||
|
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
args["warmstart"] = true
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
args["upper-bound"] = 0.1
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
separator()
|
||||||
|
|
||||||
|
return 0
|
||||||
|
end
|
||||||
|
|
||||||
|
@testset "Groups with(out) (T)" begin
|
||||||
|
|
||||||
|
@testset "GAPGroups" begin
|
||||||
|
args = Dict(
|
||||||
|
"Higman" => true,
|
||||||
|
"iterations"=>5000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>true,
|
||||||
|
)
|
||||||
|
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
|
||||||
|
args = Dict(
|
||||||
|
"Caprace" => true,
|
||||||
|
"iterations"=>5000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>true,
|
||||||
|
)
|
||||||
|
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
|
||||||
|
args = Dict(
|
||||||
|
"MCG" => 3,
|
||||||
|
"iterations"=>5000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>true,
|
||||||
|
)
|
||||||
|
|
||||||
|
G = PropertyTGroup(args)
|
||||||
|
@test main(G) == false
|
||||||
|
end
|
||||||
|
|
||||||
|
@testset "SLn's" begin
|
||||||
|
@testset "Non-Symmetrized" begin
|
||||||
|
|
||||||
|
args = Dict(
|
||||||
|
"SL" => 2,
|
||||||
|
"p" => 3,
|
||||||
|
"X" => false,
|
||||||
|
"iterations"=>50000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>true,
|
||||||
|
)
|
||||||
|
|
||||||
|
SL_tests(args)
|
||||||
|
end
|
||||||
|
|
||||||
|
@testset "Symmetrized" begin
|
||||||
|
|
||||||
|
args = Dict(
|
||||||
|
"SL" => 2,
|
||||||
|
"p" => 3,
|
||||||
|
"X" => false,
|
||||||
|
"iterations"=>20000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>false,
|
||||||
|
)
|
||||||
|
|
||||||
|
SL_tests(args)
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
@testset "SAutF_n's" begin
|
||||||
|
|
||||||
|
@testset "Non-Symmetrized" begin
|
||||||
|
|
||||||
|
args = Dict(
|
||||||
|
"SAut" => 2,
|
||||||
|
"iterations"=>5000,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>true,
|
||||||
|
)
|
||||||
|
SAut_tests(args)
|
||||||
|
end
|
||||||
|
|
||||||
|
@testset "Symmetrized" begin
|
||||||
|
args = Dict(
|
||||||
|
"SAut" => 3,
|
||||||
|
"iterations"=>500,
|
||||||
|
"tol"=>1e-7,
|
||||||
|
"upper-bound"=>Inf,
|
||||||
|
"cpus"=>2,
|
||||||
|
"radius"=>2,
|
||||||
|
"warmstart"=>false,
|
||||||
|
"nosymmetry"=>false,
|
||||||
|
)
|
||||||
|
SAut_tests(args)
|
||||||
|
end
|
||||||
|
end
|
||||||
|
|
||||||
|
|
||||||
|
end
|
Loading…
Reference in New Issue
Block a user