local-implicit-example-geometries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "98a4bf41",
   "metadata": {},
   "source": [
    "Wave Equation\n",
    "===\n",
    "\n",
    "We solve the first order wave equation by a matrix-free explicit DG method.\n",
    "\n",
    "\\begin{eqnarray*}\n",
    "\\frac{\\partial p}{\\partial t} & = & \\operatorname{div} u \\\\\n",
    "\\frac{\\partial u}{\\partial t} & = & \\nabla p\n",
    "\\end{eqnarray*}\n",
    "\n",
    "We obtain the ODE \n",
    "\\begin{eqnarray*}\n",
    "M_p \\dot{p} & = & -B^T u \\\\\n",
    "M_u \\dot{u} & = & B p\n",
    "\\end{eqnarray*}\n",
    "\n",
    "form a simple DG version with central fluxes. The discrete gradient $B$ is defined by the bilinear-form\n",
    "$$\n",
    "b(p,v) = \\sum_{T}\n",
    "\\Big\\{ \\int_T \\nabla p  \\, v + \\int_{\\partial T} (\\{ p \\} - p) \\, v_n \\, ds \\Big\\} \n",
    "$$\n",
    "\n",
    "It conserves energy, but is not free of spurious modes.\n",
    "\n",
    "Hesthaven+Warbuton: Nodal Discontinuous Galerkin Methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eceed1a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ngsolve import *\n",
    "from ngsolve.webgui import Draw\n",
    "from netgen.webgui import Draw as DrawGeo\n",
    "from ngsolve.krylovspace import CGSolver\n",
    "from netgen.occ import *\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9041588",
   "metadata": {},
   "source": [
    "### Different geometries are possible (1line, 2line, hole, box 3d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "845da266",
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_mesh(geo, dim, extrude):\n",
    "    if geo == \"hole\":\n",
    "        box = MoveTo(-1,-1).Rectangle(2,2).Face()\n",
    "        implicit = MoveTo(0.1,-0.005).Rectangle(0.3,0.005).Face() + \\\n",
    "            MoveTo(0.2,-0.15).Rectangle(0.005, 0.3).Face() \n",
    "        circ = Circle((0.5, 0), r = 0.15).Face()\n",
    "        circ.maxh = h/4\n",
    "        shape = box - circ - implicit\n",
    "    elif geo == \"1line\":\n",
    "        rect = MoveTo(-1,-1).Rectangle(2.5,2).Face()\n",
    "        hole = MoveTo(0.5,0.01).Rectangle(0.001,0.8).Face()\n",
    "        shape = rect-hole\n",
    "    elif geo == \"2line\":\n",
    "        rect = MoveTo(-0.5,-0.5).Rectangle(1.5,1).Face()\n",
    "        hole = MoveTo(0.5,0.01).Rectangle(0.001,0.4).Face() + \\\n",
    "            MoveTo(0.5,-0.41).Rectangle(0.001,0.4).Face()\n",
    "        shape = rect-hole\n",
    "    elif geo == \"box\": \n",
    "        box = Box((-1,-1,-1), (1,1,0))\n",
    "        hole = Sphere( Pnt(0.5, 0, 0), 0.2 )\n",
    "        shape = box - hole\n",
    "        shape.faces.name = \"outer\"\n",
    "        return shape\n",
    "    \n",
    "    if dim == 3:\n",
    "        shape = shape.Extrude(extrude)\n",
    "    return shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b56c36a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "dim = 2\n",
    "extrude = 0.05\n",
    "h = 0.05\n",
    "geo = \"2line\" # hole, 1line, 2line, box\n",
    "\n",
    "shape = create_mesh(geo, dim, extrude)\n",
    "\n",
    "shape = OCCGeometry(shape, dim = dim)\n",
    "\n",
    "mesh = Mesh(shape.GenerateMesh(maxh = h)).Curve(3)\n",
    "Draw(mesh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbc8a79f",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"boundaries: \", mesh.GetBoundaries())\n",
    "print(\"materials: \", mesh.GetMaterials())\n",
    "print(\"number elements: \", mesh.ne)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19bd5a70",
   "metadata": {},
   "outputs": [],
   "source": [
    "order = 3\n",
    "fes_p = L2(mesh, order=order+1, all_dofs_together=True, dgjumps=True) \n",
    "fes_u = VectorL2(mesh, order=order, piola=True, dgjumps=True)\n",
    "fes_tr = FacetFESpace(mesh, order=order+1)\n",
    "fes = fes_p * fes_u\n",
    "\n",
    "traceop = fes_p.TraceOperator(fes_tr, average=True) \n",
    "\n",
    "gfu = GridFunction(fes_u)\n",
    "gfp = GridFunction(fes_p)\n",
    "gftr = GridFunction(fes_tr)\n",
    "\n",
    "gfp.Set( exp(-400*(x**2+y**2+z**2)))\n",
    "gftr.vec.data = traceop * gfp.vec\n",
    "\n",
    "p, u = fes.TrialFunction()\n",
    "q, v = fes.TestFunction()\n",
    "phat = fes_tr.TrialFunction()\n",
    "\n",
    "n = specialcf.normal(mesh.dim)\n",
    "dS = dx(skeleton=True)   \n",
    "def jump(p): return p.Other()-p\n",
    "def avgn(v): return 0.5*(v*n-v.Other()*n.Other())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a3d6fd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "embp, embu = fes.embeddings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8559bf3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "tend = 2\n",
    "dt = 0.2 * h / (order+1)**2\n",
    "print (\"dt = \", dt)\n",
    "print(\"Number of steps: \", tend/dt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aaff4af6",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"fes ndofs: \", fes.ndof)\n",
    "print(\"fes_u ndofs: \", fes_u.ndof)\n",
    "print(\"fes_p ndofs: \", fes_p.ndof)\n",
    "print(\"fes_tr ndofs: \", fes_tr.ndof)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "24eb1791",
   "metadata": {},
   "outputs": [],
   "source": [
    "if dim == 2:\n",
    "    Draw (gfp, order=3)\n",
    "else:\n",
    "    gftr.vec.data = traceop * gfp.vec\n",
    "    Draw (gftr, draw_vol=False, order=3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a647e8bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "mesh.ne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "edb28e75",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "F = specialcf.JacobianMatrix(mesh.dim)\n",
    "Finv = Inv(F)\n",
    "detF = Det(F)\n",
    "Norm_Finv = Norm(Finv)\n",
    "el_norms = Integrate(Norm_Finv*1/detF.Norm(), mesh, element_wise=True)\n",
    "el_norms_numpy = np.array(el_norms)\n",
    "\n",
    "sorted_el_norms = -np.sort(-el_norms_numpy) #sort descending\n",
    "ref_norm = el_norms_numpy.mean()# using elements > mean \n",
    "impl_els = np.where(el_norms_numpy > ref_norm, 1, 0)\n",
    "    \n",
    "print('max', max(el_norms_numpy))\n",
    "print('min', min(el_norms_numpy))\n",
    "print('mean', el_norms_numpy.mean())\n",
    "print('median', np.median(el_norms_numpy))\n",
    "print('ref_norm', ref_norm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb83f004",
   "metadata": {},
   "outputs": [],
   "source": [
    "ba_implicit_els = BitArray(mesh.ne)\n",
    "ba_explicit_els = BitArray(mesh.ne)\n",
    "ba_interface_edges = BitArray(mesh.nedge)\n",
    "ba_explicit_edges = BitArray(mesh.nedge)\n",
    "ba_implicit_edges = BitArray(mesh.nedge)\n",
    "\n",
    "ba_implicit_els[:] = 0\n",
    "ba_explicit_els[:] = 0\n",
    "ba_interface_edges[:] = 0\n",
    "ba_explicit_edges[:] = 0\n",
    "ba_implicit_edges[:] = 0\n",
    "\n",
    "for el in mesh.Elements():\n",
    "    if impl_els[el.nr] == 1:\n",
    "        ba_implicit_els[el.nr] = 1\n",
    "        for e in el.edges:\n",
    "            ba_implicit_edges[e.nr] = 1\n",
    "    else:\n",
    "        ba_explicit_els[el.nr] = 1\n",
    "        for e in el.edges:\n",
    "            ba_explicit_edges[e.nr] = 1\n",
    "        \n",
    "ba_interface_edges = ba_explicit_edges & ba_implicit_edges     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b8b01a27",
   "metadata": {},
   "outputs": [],
   "source": [
    "ba_local_implicit_dofs = BitArray(fes.ndof)\n",
    "ba_local_implicit_dofs[:] = 0\n",
    "\n",
    "for el in mesh.Elements():\n",
    "    if ba_implicit_els[el.nr] == 1:\n",
    "        for nr in fes.GetDofNrs(el):\n",
    "            ba_local_implicit_dofs[nr] = 1\n",
    "    if ba_explicit_els[el.nr] == 1:\n",
    "        for e in el.edges:\n",
    "            if ba_interface_edges[e.nr] == 1:\n",
    "                for nr in fes.GetDofNrs(el):\n",
    "                    ba_local_implicit_dofs[nr] = 1\n",
    "\n",
    "ba_local_implicit_dofs_u = BitArray(fes_u.ndof)\n",
    "ba_local_implicit_dofs_u[:] = 0\n",
    "\n",
    "for el in mesh.Elements():\n",
    "    if ba_implicit_els[el.nr] == 1:\n",
    "        for nr in fes_u.GetDofNrs(el):\n",
    "            ba_local_implicit_dofs_u[nr] = 1\n",
    "    if ba_explicit_els[el.nr] == 1:\n",
    "        for e in el.edges:\n",
    "            if ba_interface_edges[e.nr] == 1:\n",
    "                for nr in fes_u.GetDofNrs(el):\n",
    "                    ba_local_implicit_dofs_u[nr] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "725e853a",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = BilinearForm(fes)\n",
    "A += -p*q*dx +u*v*dx \n",
    "A += dt/2*(grad(p)*v + grad(q)*u)*dx\n",
    "A += dt/2*(jump(p)*avgn(v)+jump(q)*avgn(u)) * dS\n",
    "A.Assemble()\n",
    "\n",
    "p1, q1 = fes_p.TnT()\n",
    "u1, v1 = fes_u.TnT()\n",
    "phat1, qhat1 = fes_tr.TnT()\n",
    "Bel = BilinearForm(trialspace=fes_p, testspace=fes_u, geom_free = True)\n",
    "Bel += grad(p1)*v1 * dx -p1*(v1*n) * dx(element_boundary=True)\n",
    "Bel.Assemble()\n",
    "Btr = BilinearForm(trialspace=fes_tr, testspace=fes_u, geom_free = True)\n",
    "Btr += phat1 * (v1*n) *dx(element_boundary=True)\n",
    "Btr.Assemble();\n",
    "\n",
    "B = Bel.mat + Btr.mat @ traceop\n",
    "B_T = B.T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40c11b19",
   "metadata": {},
   "outputs": [],
   "source": [
    "massu = fes_u.Mass(1)\n",
    "invmassu = fes_u.Mass(1).Inverse()\n",
    "invmassp = fes_p.Mass(1).Inverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a14dd59c",
   "metadata": {},
   "outputs": [],
   "source": [
    "Ps = Projector(ba_local_implicit_dofs_u, True)   # projection to small\n",
    "Pl = Projector(ba_local_implicit_dofs_u, False)  # projection to large\n",
    "B_e = Pl @ B\n",
    "B_i = Ps @ B\n",
    "\n",
    "print (\"local implicit dofs: \", ba_local_implicit_dofs.NumSet(),\"/\",len(ba_local_implicit_dofs))\n",
    "print (\"local implicit dofs of fes u: \", ba_local_implicit_dofs_u.NumSet(),\"/\",len(ba_local_implicit_dofs_u))\n",
    "print (\"shape B_e: \", B_e.shape)\n",
    "print (\"shape B_i: \", B_i.shape)\n",
    "print (\"shape Ps: \", Ps.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9c2994f",
   "metadata": {},
   "outputs": [],
   "source": [
    "invA = A.mat.Inverse(freedofs=ba_local_implicit_dofs, inverse=\"sparsecholesky\")\n",
    "\n",
    "# delete non zeros elements of matrix to speed up matrix multiplication\n",
    "Anze = A.mat.DeleteZeroElements(10e-12)\n",
    "invAnze = Anze.Inverse(freedofs=ba_local_implicit_dofs, inverse=\"sparsecholesky\")\n",
    "invmstar = embu.T @ invAnze @ embu\n",
    "mstarloc = massu + dt*dt/4*B_i @ invmassp @ B_T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73bb02f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "A.mat.nze, invA.nze, Anze.nze"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ef74145d",
   "metadata": {},
   "outputs": [],
   "source": [
    "invmassuB = invmassu @ B\n",
    "invmasspB_T = invmassp @ B_T\n",
    "invmstar_mstar = invmstar @ mstarloc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d7d59ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "# visulaize implicit dofs\n",
    "from time import sleep\n",
    "ba_gfu = BitArray(fes.ndof)\n",
    "ba_gfu[:] = 0\n",
    "gfuim = GridFunction(fes)\n",
    "gfuim.vec[:] = 0\n",
    "for i in range(len(ba_local_implicit_dofs)):\n",
    "    if ba_local_implicit_dofs[i] == 1:\n",
    "        gfuim.vec.data[i] = 1\n",
    "        \n",
    "scene1 = Draw(gfuim.components[0], mesh)\n",
    "scene2 = Draw(gfuim.components[1], mesh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aec05549",
   "metadata": {},
   "outputs": [],
   "source": [
    "gfp.Set( exp(-400*(x**2+y**2+z**2)))\n",
    "gfu.vec[:] = 0\n",
    "gfp_halfstep = gfp.vec.CreateVector()\n",
    "gfuold = gfu.vec.CreateVector()\n",
    "res = gfu.vec.CreateVector()\n",
    "\n",
    "if dim == 2:\n",
    "    scene = Draw (gfp, order=3, deformation=True);\n",
    "else:\n",
    "    scene = Draw (gftr, draw_vol=False, order=3);\n",
    "    \n",
    "t = 0\n",
    "tend = 2\n",
    "cnt = 0\n",
    "loop = tqdm([i*dt for i in range(int(tend/dt))])\n",
    "with TaskManager():#pajetrace=10**8):\n",
    "    for i in loop:\n",
    "        \n",
    "        gfp_halfstep.data = gfp.vec - dt/2 * invmassp @ B.T * gfu.vec\n",
    "        \n",
    "        res.data = dt * B_e * gfp_halfstep + dt/2 * B_i * (gfp_halfstep + gfp.vec) + massu * gfu.vec\n",
    "        gfuold.data = invmassu * res \n",
    "        gfu.vec.data = gfuold\n",
    "        gfu.vec.data += invmstar * (res - mstarloc * gfuold)\n",
    "        gfp.vec.data = gfp_halfstep - dt/2 * invmassp @ B.T * gfu.vec\n",
    "        cnt = cnt+1\n",
    "        if cnt%10 == 0:\n",
    "            if dim == 3:\n",
    "                gftr.vec.data = traceop * gfp.vec\n",
    "        scene.Redraw()\n",
    "        loop.set_description(f'Time step {i/dt:.0f}')\n",
    "        loop.set_postfix_str(f'Time {i:.4f} seconds')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db8d3a4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.sparse as sp\n",
    "import matplotlib.pylab as plt\n",
    "rows,cols,vals = A.mat.COO()\n",
    "a = sp.csr_matrix((vals,(rows,cols)))\n",
    "plt.spy(a)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "048458bd",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}