"""Integer interval replay of the regular-pentagon Neumann flux certificate. Only the Python standard library is used. Floating-point FEM output serves solely as integer trial and stream coefficients supplied in the witness. """ import argparse import gzip import json from fractions import Fraction from math import isqrt from pathlib import Path from flux_mesh import Mesh, elevate, gradient, index_map, indices, local_particular, mass_integer BITS = 150 UNIT = 1 << BITS def up(a,b): return -((-a)//b) class Interval: __slots__ = ('lo','hi') def __init__(self,lo,hi): assert lo<=hi self.lo,self.hi = lo,hi @staticmethod def point(num,den=1): assert den>0 return Interval((num*UNIT)//den,up(num*UNIT,den)) def __add__(self,x): if isinstance(x,int): y=x*UNIT return Interval(self.lo+y,self.hi+y) return Interval(self.lo+x.lo,self.hi+x.hi) __radd__=__add__ def __neg__(self): return Interval(-self.hi,-self.lo) def __sub__(self,x): return self+(-x) def __rsub__(self,x): return (-self)+x def __mul__(self,x): if isinstance(x,int): a,b=self.lo*x,self.hi*x return Interval(min(a,b),max(a,b)) t=(self.lo*x.lo,self.lo*x.hi,self.hi*x.lo,self.hi*x.hi) return Interval(min(t)//UNIT,up(max(t),UNIT)) __rmul__=__mul__ def __truediv__(self,x): if isinstance(x,int): assert x>0 return Interval(self.lo//x,up(self.hi,x)) assert x.lo>0 return self*Interval(UNIT**2//x.hi,up(UNIT**2,x.lo)) def sqrt(self): assert self.lo>=0 return Interval(isqrt(self.lo*UNIT),isqrt(self.hi*UNIT)+1) def split(v): mids = [] radius = 0 for x in v: if isinstance(x,int): mids.append(x*UNIT) else: m=(x.lo+x.hi)//2 mids.append(m) radius=max(radius,x.hi-m) return mids,radius,max(map(abs,mids)) def integral_from_centers(val,den,r1,m1,r2,m2): # The reference triangle has area 1/2. A Bernstein polynomial is a # convex combination of its coefficients, so the sup deviation from the # midpoint polynomial is bounded by the largest coefficient radius. err=up(r1*m2+r2*m1+r1*r2,2*UNIT) return Interval(val//(UNIT*den)-err,up(val,UNIT*den)+err) def inner_products(x,p,y=None): weights,den=mass_integer(p) xv,rx,mx=split(x) ax=[sum(wi*xi for wi,xi in zip(row,xv)) for row in weights] xx=integral_from_centers(sum(xi*wi for xi,wi in zip(xv,ax)),den,rx,mx,rx,mx) if y is None: return xx yv,ry,my=split(y) ay=[sum(wi*yi for wi,yi in zip(row,yv)) for row in weights] xy=integral_from_centers(sum(yi*wi for yi,wi in zip(yv,ax)),den,rx,mx,ry,my) yy=integral_from_centers(sum(yi*wi for yi,wi in zip(yv,ay)),den,ry,my,ry,my) return xx,xy,yy def form(coeffs,inner): a,b,c=coeffs xx,xy,yy=inner return a*xx+2*b*xy+c*yy def audit_lift(p): # An independent exact local divergence and normal-trace check. source=[Fraction(3*i*i+2*i-5,7+i) for i in range(len(indices(p)))] mean=sum(source)/((p+1)*(p+2)) e0,e1=Fraction(17,7),Fraction(-4,3) e2=mean-e0-e1 px,py=local_particular(source,(e0,e1,e2),p) m=p+1 look=index_map(m) dx=gradient(px,m)[0] dy=gradient(py,m)[1] assert all(x+y==f for x,y,f in zip(dx,dy,source)) assert all(-py[look[m-j,j,0]]==e0 for j in range(m+1)) assert all(px[look[0,m-j,j]]+py[look[0,m-j,j]]==e1 for j in range(m+1)) assert all(-px[look[j,0,m-j]]==e2 for j in range(m+1)) def verify(data): assert data['format']==1 p=data['degree'] mesh=Mesh(data['depth']) assert isinstance(p,int) and p>=1 audit_lift(p) s5=Interval.point(5).sqrt() s2=(5+s5)/8 area=5*s2.sqrt()/2 cells,fix,N=mesh.dofs(p,[mesh.axis]) wcells,wfix,Nw=mesh.dofs(p+2,mesh.top) def coefficients(key,n,fixed): nums=data[key] assert len(nums)==n and all(isinstance(x,int) for x in nums) assert all(nums[i]==0 for i in fixed) return [Interval.point(x,1<0 for j,h in geos) jac_sum=sum(j for j,h in geos) assert 2*jac_sum.lo<=5*UNIT<=2*jac_sum.hi values=[[trial[i] for i in cell] for cell in cells] grads=[gradient(v,p) for v in values] mass=0 energy=0 for v,(gx,gy),(j,h) in zip(values,grads,geos): mass+=j*inner_products(v,p) energy+=form(h,inner_products(gx,p-1,gy)) rho=energy/mass assert 0=0 eta2=defect/mass lower=rho/(1+11*eta2/(rho*(11-rho))) grad_tail=eta2.sqrt()*11/(11-rho) return {'mass':mass,'rho':rho,'squared_dual_residual_bound':eta2, 'lambda_lower':lower,'F_lower':area*lower,'F_upper':area*rho, 'projected_energy_norm_error_upper':grad_tail, 'projected_mass_norm_error_upper':grad_tail/Interval.point(11).sqrt()} def endpoint(z,places,upper): a=up(z*10**places,UNIT) if upper else (z*10**places)//UNIT s=str(abs(a)).zfill(places+1) return ('-' if a<0 else '')+s[:-places]+'.'+s[-places:] if __name__=='__main__': parser=argparse.ArgumentParser() parser.add_argument('witness',nargs='?',type=Path, default=Path(__file__).with_name('flux-witness.json')) args=parser.parse_args() raw = args.witness.read_bytes() data = json.loads(gzip.decompress(raw) if args.witness.suffix == '.gz' else raw) result=verify(data) for name,value in result.items(): print(name,endpoint(value.lo,24,False),endpoint(value.hi,24,True)) if args.witness.name in ('flux-witness.json', 'flux-witness.json.gz'): assert result['lambda_lower'].lo*1000000 > 4354463*UNIT scale=10**17 assert result['F_lower'].lo*scale>1035335162333505933*UNIT assert result['F_upper'].hi*scale<1035335162333505954*UNIT