SharedHnorm.ipynbOpen in CoCalc
Jupyter notebook Hnorm.ipynb
import numpy as np
from cvxopt import matrix, solvers
def Hnorm(A):
    # Regner ut Hilbert-norm til numpy matrise A
    rad, kol = A.shape
    nullr = np.zeros((rad,rad))
    nullk = np.zeros((kol,kol))
    C = np.bmat([[nullr,A],[A.T,nullk]])

    h0 = [ -0.5*matrix(C) ]

    dim = rad+kol
    c = matrix(np.ones(dim,))
    # Vil lage diagonalmatriser A_i med 1 på plass (i,i), 0 ellers
    diagonal = np.zeros(dim,)
    diagonal[0] = 1
    A0 = np.diag(diagonal)
    G = A0
    for i in xrange(1,dim):
        A0 = np.diag(np.roll(diagonal,i))
        G = np.bmat([[G],[A0]])
    # G0 er nå blokk matrise med A_i'ene stabla nedover i radene.
    G0 = [ matrix(-1.0*G) ]
    solvers.options['show_progress']=False
    solvers.options['abstol'] = 1e-11
    solvers.options['reltol'] = 1e-10
    sol = solvers.sdp(c, Gs=G0, hs=h0)
    norm = -1
    if sol['status'] == 'optimal':
        norm = sol['primal objective']
    return norm

def ekstrem_ell_infty_recursive(N):
    ekstrem_punkt = np.zeros((2**(N-1),N),dtype=np.int)
    if N == 1:
        ekstrem_punkt[0] = 1
    else:
        ekstrem_punkt[:,0] = np.ones((2**(N-1),),dtype=np.int)
        E = ekstrem_ell_infty_recursive(N-1)
        ekstrem_punkt[:2**(N-2),1:] = E.copy()
        ekstrem_punkt[2**(N-2):,1:] = -1*E.copy()   
    return ekstrem_punkt
    
def ekstrem_ell_infty2(N):
    return ekstrem_ell_infty_recursive(N).transpose()

def Mnorm(A):
    # Regn ut norm max(|Ax|_1, x kolonne i E)
    rad, kol = A.shape
    E = ekstrem_ell_infty2(kol)

    # Ta absolutt verdi av elementene og summer kolonnevis
    return np.max(np.sum(np.abs(A*E),axis=0))
    # Eventuelt 
    # return reduce(max,np.sum(np.abs(A*E),axis=0))

def finnKG(matrise):
    """Tar ei matrise på formen '{{1,1},{1,-1}}' (en streng)
    og returnerer Mnorm, Hnorm og forholdet Hnorm/Mnorm"""
    M = matrise
    M = M.replace('},{',';')
    M = M.replace('{{','[')
    M = M.replace('}}',']')
    M = np.mat(M)
    norm_M = Mnorm(M)
    norm_H = Hnorm(M)
    KG = norm_H/norm_M
    return (norm_M, norm_H, KG)
be1='{{-1,-1,0,0,0,1,1},{-1,1,0,1,0,1,0},{0,0,-1,-1,0,1,1},{0,1,-1,0,1,0,1},{1,0,0,0,1,1,1},{0,0,0,1,1,1,1},{0,1,0,1,0,0,-2}}'

be2='{{-1,-1,0,0,1,1,0},{-1,1,0,1,0,1,0},{0,1,-1,-1,0,0,1},{0,0,-1,1,1,0,1},{1,1,0,0,1,1,0},{1,1,0,1,0,1,0},{1,0,0,0,0,1,-2}}'

be3='{{-1,-1,0,0,1,1,0},{-1,0,0,0,1,1,1},{0,0,-1,-1,1,0,1},{0,0,-1,1,0,1,1},{1,0,0,0,1,1,1},{0,0,1,1,0,1,1},{1,0,0,0,0,1,-2}}'

be4='{{-1,-1,0,0,1,1,0},{-1,0,0,1,1,1,0},{0,0,-1,-1,1,0,1},{0,0,-1,0,1,1,1},{0,0,0,1,1,1,1},{0,1,0,1,1,1,0},{1,0,0,1,0,0,-2}}'

be5='{{-1,-1,0,0,1,0,1},{-1,1,0,1,1,0,0},{0,1,-1,-1,0,0,1},{0,1,-1,0,1,1,0},{0,1,1,0,1,1,0},{0,0,1,1,1,1,0},{1,0,1,0,0,0,-2}}'

be6='{{-1,-1,0,1,0,1,0},{-1,1,0,1,1,0,0},{0,0,-1,-1,1,1,0},{0,1,-1,0,0,1,1},{0,1,1,1,1,0,0},{0,0,0,1,1,1,1},{0,1,1,0,0,0,-2}}'

be7='{{-1,-1,0,1,0,1,0},{-1,1,0,1,1,0,0},{0,1,-1,-1,1,0,0},{0,0,-1,1,1,0,1},{0,1,0,1,1,1,0},{1,1,0,1,0,1,0},{1,0,1,0,0,0,-2}}'

be8='{{-1,-1,0,1,0,1,0},{-1,1,0,0,1,0,1},{0,1,-1,-1,0,0,1},{0,1,-1,0,1,0,1},{0,0,0,1,1,1,1},{1,0,0,1,1,1,0},{1,0,1,0,0,0,-2}}'

be9='{{-1,-1,0,1,0,0,1},{-1,0,0,1,1,0,1},{0,0,-1,-1,1,0,1},{0,1,-1,0,1,1,0},{0,0,1,1,1,1,0},{1,1,0,0,1,1,0},{1,0,0,1,0,0,-2}}'

be10='{{-1,-1,0,0,1,0,1},{-1,0,0,1,1,0,1},{0,0,-1,-1,0,1,1},{0,1,-1,0,1,1,0},{1,1,0,0,1,1,0},{1,1,0,0,1,1,0},{1,1,0,0,0,0,-2}}'

be11='{{-1,-1,0,1,0,0,1},{-1,1,0,0,0,1,1},{0,1,-1,-1,1,0,0},{0,0,-1,1,1,0,1},{1,1,0,0,1,1,0},{0,1,0,0,1,1,1},{1,0,0,0,0,1,-2}}'

be12='{{-1,-1,0,0,1,0,1},{-1,0,0,1,0,1,1},{0,1,-1,-1,0,0,1},{0,0,-1,1,1,0,1},{0,0,1,1,1,1,0},{0,1,1,0,1,1,0},{1,0,1,0,0,0,-2}}'

be13='{{-1,-1,0,0,1,1,0},{-1,0,0,1,1,0,1},{0,0,-1,-1,1,0,1},{0,1,-1,0,1,0,1},{1,1,0,0,1,1,0},{1,1,0,0,0,1,1},{1,0,0,1,0,0,-2}}'

be14='{{-1,-1,0,1,0,1,0},{-1,0,0,1,1,0,1},{0,1,-1,-1,0,1,0},{0,0,-1,1,1,0,1},{0,0,1,0,1,1,1},{0,1,1,0,0,1,1},{0,1,1,0,0,0,-2}}'

be15='{{-1,-1,0,0,1,0,1},{-1,1,0,1,0,0,1},{0,1,-1,-1,0,1,0},{0,0,-1,1,1,0,1},{0,0,0,1,1,1,1},{1,0,0,0,1,1,1},{0,1,1,0,0,0,-2}}'

map(finnKG,[be1,be2,be3,be4,be5,be6,be7,be8,be9,be10,be11,be12,be13,be14,be15])
[(20, 21.00707851083401, 1.0503539255417005), (18, 19.63298430706519, 1.0907213503925106), (20, 20.484052752611067, 1.0242026376305533), (22, 23.121144884335962, 1.0509611311061802), (20, 21.54762332439839, 1.0773811662199195), (20, 21.174465236036323, 1.058723261801816), (22, 22.010954756338805, 1.0004979434699457), (22, 22.978354043638657, 1.0444706383472118), (18, 20.743272419168644, 1.1524040232871469), (22, 22.88598288587994, 1.0402719493581791), (20, 22.08982145803464, 1.1044910729017319), (20, 21.56799783974171, 1.0783998919870856), (20, 21.179564947185845, 1.0589782473592924), (20, 20.857282573658956, 1.0428641286829479), (20, 21.48784420165415, 1.0743922100827075)]
be1='{{-1,-1,0,0,0,1,0,1,0},{-1,1,0,0,0,0,0,1,1},{0,0,-1,-1,1,0,1,0,0},{0,0,-1,0,1,1,0,1,0},{0,0,0,1,1,0,1,0,1},{1,0,0,0,0,2,0,-1,0},{0,0,1,0,2,0,-1,0,0},{1,0,0,0,2,-1,0,0,0},{0,0,1,0,1,1,1,0,0}}'
map(finnKG,[be1])
[(18, 24.14927675247584, 1.3416264862486578)]
be1='{{-1,-1,0,1,1,0,0,0},{-1,1,0,0,0,1,1,0},{0,1,-1,-1,0,0,1,0},{0,0,-1,1,1,0,1,0},{1,0,1,0,0,0,1,1},{1,0,0,0,1,1,-1,0},{0,0,0,1,0,-1,1,1},{0,1,1,0,1,1,0,0}}'

be2='{{-1,-1,0,1,0,0,1,0},{-1,1,0,0,0,1,0,1},{0,1,-1,-1,1,0,0,0},{0,0,-1,1,0,1,0,1},{0,0,1,1,1,0,0,1},{1,0,0,0,1,1,-1,0},{0,1,0,0,0,-1,1,1},{1,0,1,0,1,0,1,0}}'

be3='{{-1,-1,0,1,0,1,0,0},{-1,0,0,0,1,1,0,1},{0,1,-1,-1,0,0,0,1},{0,1,-1,1,0,0,0,1},{1,0,0,0,1,1,0,1},{1,0,1,0,1,0,-1,0},{1,1,0,1,0,-1,0,0},{1,0,1,0,1,0,1,0}}'
map(finnKG,[be1,be2,be3])
[(16, 21.045353606250494, 1.3153346003906559), (16, 21.378578905466036, 1.3361611815916272), (16, 21.166010488242122, 1.3228756555151326)]
be1='{{0,1,0,0,0,1,-1,1},{0,0,1,1,-1,0,1,0},{0,0,1,-1,1,0,0,-1},{0,1,0,1,0,-1,0,-1},{0,0,0,1,1,0,0,0},{0,0,0,0,1,1,0,0},{0,0,0,0,0,1,1,0},{0,0,0,0,0,0,1,1}}'
map(finnKG,[be1])
[(12, 16.40360556659504, 1.3669671305495867)]


map(finnKG,[be1,be2,be3,be4,be5,be6,be7,be8,be9,be10,be11,be12,be13,be14,be15,be16,be17])
[(10, 13.78613295437191, 1.378613295437191), (10, 13.78613295437191, 1.378613295437191), (10, 13.786132954371908, 1.3786132954371908), (10, 13.786132954371906, 1.3786132954371906), (10, 13.786132954371908, 1.3786132954371908), (10, 13.786132954371912, 1.3786132954371912), (10, 13.786132954371906, 1.3786132954371906), (10, 13.786132954371903, 1.3786132954371904), (10, 13.786132954371906, 1.3786132954371906), (10, 13.786132954371903, 1.3786132954371904), (10, 13.786132954371908, 1.3786132954371908), (10, 13.786132954371903, 1.3786132954371904), (10, 13.786132954371912, 1.3786132954371912), (10, 13.786132954371908, 1.3786132954371908), (10, 13.786132954371903, 1.3786132954371904), (10, 13.786132954371903, 1.3786132954371904), (10, 13.786132954371906, 1.3786132954371906)]

map(finnKG,[be1,be2,be3,be4,be5,be6,be7,be8,be9,be10,be11,be12,be13,be14])
[(12, 16.255158017780474, 1.354596501481706), (24, 32.17487752066413, 1.3406198966943388), (16, 21.621441920790097, 1.351340120049381), (14, 18.908814899693898, 1.3506296356924212), (12, 16.4388875812209, 1.369907298435075), (20, 27.003114182633407, 1.3501557091316703), (26, 34.16542074336297, 1.314054643975499), (20, 26.837975818963397, 1.3418987909481699), (14, 18.830176081134937, 1.345012577223924), (18, 24.168575628229462, 1.342698646012748), (16, 21.953256209289318, 1.3720785130805824), (24, 31.861494014148498, 1.3275622505895208), (16, 21.647066321575995, 1.3529416450984997), (12, 16.55462627640556, 1.3795521897004634)]

map(finnKG,[be1,be2,be3])
[(10, 14.109430218654271, 1.410943021865427), (10, 14.109430218654275, 1.4109430218654275), (10, 14.109430218654271, 1.410943021865427)]

map(finnKG,[be1,be2,be3,be4,be5,be6,be7,be8,be9,be10,be11,be12,be13,be14])
[(16, 22.158147499425723, 1.3848842187141077), (20, 26.983643782275763, 1.349182189113788), (14, 19.408778662234116, 1.3863413330167227), (20, 26.95532611043585, 1.3477663055217923), (22, 29.296545002702146, 1.3316611364864612), (16, 21.88555847325082, 1.3678474045781763), (14, 19.503116341244898, 1.3930797386603497), (14, 19.17087458380834, 1.3693481845577387), (18, 24.146967933830815, 1.3414982185461564), (14, 19.280799161922427, 1.3771999401373163), (16, 21.799600645450482, 1.3624750403406551), (16, 22.08831379764171, 1.380519612352607), (32, 43.16620310138438, 1.348943846918262), (14, 19.02727013201721, 1.359090723715515)]

















map(finnKG,[be14])

map(finnKG,[be1])
WARNING: Some output was deleted.
























map(finnKG,[be1])
[(8, 11.262193104312297, 1.4077741380390372)]












be180='{{0,0,0,0,0,0,0,0},{1,1,0,0,1,1,0,0},{0,0,-1,0,1,0,0,0},{0,0,0,-1,0,1,0,0},{1,0,0,1,-1,0,0,1},{0,1,1,0,0,-1,1,0},{0,0,1,1,1,0,-1,0},{0,0,1,1,0,1,0,-1}}'
map(finnKG,[be180])
[(12, 16.9705624961966, 1.4142135413497166)]