{ "cells": [ { "cell_type": "markdown", "id": "3d37be00", "metadata": {}, "source": [ "## CSS.205.1 Toolkit for TCS 2023 - Spectral Methods" ] }, { "cell_type": "markdown", "id": "71e86f4e", "metadata": {}, "source": [ "Jupyter Notebook for Spectral Methods module of course using the tools developed by Dan Spielman. References and sources:\n", "* Dan Spielman's course on Spectral Methods @ Yale University, 2019.\n", "* Laplacians Package (by Dan Spielman)\n", "\n", "If you want to try using this, you will need to install Jupyter (via Python), Julia and IJulia. You also need Spielman's package, called Laplacians.jl. It may be added in Julia via\n", "\n", "Using Pkg\n", "Pkg.add(\"Laplacians\")\n", "\n", "\n", "### Table of Contents\n", "\n", "1. Line Graphs\n", "\n", "2. Grid Graphs\n", "\n", "3. Platonic Solids\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "530ee5dd", "metadata": {}, "outputs": [], "source": [ "using Laplacians\n", "using LinearAlgebra\n", "using Plots\n", "using SparseArrays\n", "using FileIO\n", "using JLD2\n", "using Random" ] }, { "cell_type": "code", "execution_count": 2, "id": "1635c68b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Plots.GRBackend()" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gr()" ] }, { "cell_type": "markdown", "id": "631a10a2", "metadata": {}, "source": [ "# Paths / Cycles\n", "\n", "Commands for generating path and cycles\n", "* line: path_graph(#vertices)\n", "* cycle: ring_graph(#vertices)\n", "* Complete Bipartite graph on (n,n) vertices: complete_bipartite_graph(n)\n", "* Star Graph: star_graph(#vertices)\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "3d544de8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12×12 SparseMatrixCSC{Float64, Int64} with 24 stored entries:\n", " ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0\n", " 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \n", " ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \n", " ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \n", " ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \n", " ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ \n", " ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ ⋅ \n", " ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ ⋅ \n", " ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ ⋅ \n", " ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0 ⋅ \n", " ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ 1.0\n", " 1.0 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1.0 ⋅ " ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n=12\n", "M = ring_graph(n)" ] }, { "cell_type": "code", "execution_count": 4, "id": "032fe542", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12×12 Matrix{Float64}:\n", " 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0\n", " 1.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 1.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 1.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0 1.0\n", " 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Matrix(M)" ] }, { "cell_type": "code", "execution_count": 5, "id": "dee02f9b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12×12 Matrix{Float64}:\n", " 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0\n", " -1.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 2.0 -1.0\n", " -1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0 2.0" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L=Matrix(lap(M))" ] }, { "cell_type": "code", "execution_count": 6, "id": "9dcc2b08", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[-5.0813954256430024e-17, 0.2679491924311225, 0.2679491924311246, 0.9999999999999978, 1.0000000000000022, 1.9999999999999982, 2.0000000000000018, 2.9999999999999982, 3.0, 3.732050807568871, 3.732050807568877, 3.999999999999996]\n" ] } ], "source": [ "E = eigen(Matrix(L))\n", "println(E.values)" ] }, { "cell_type": "code", "execution_count": 7, "id": "9271c930", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12-element Vector{Float64}:\n", " -0.2886751345948131\n", " -0.2886751345948125\n", " -0.2886751345948128\n", " -0.28867513459481275\n", " -0.2886751345948125\n", " -0.28867513459481225\n", " -0.28867513459481275\n", " -0.2886751345948132\n", " -0.2886751345948131\n", " -0.28867513459481264\n", " -0.2886751345948132\n", " -0.28867513459481364" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E.vectors[:,1]" ] }, { "cell_type": "code", "execution_count": 8, "id": "0fcc2999", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "12-element Vector{Float64}:\n", " 0.35355339059327384\n", " 0.20412414523193048\n", " -4.411591051069787e-16\n", " -0.20412414523193162\n", " -0.3535533905932736\n", " -0.4082482904638627\n", " -0.35355339059327395\n", " -0.20412414523193217\n", " -7.372821896687958e-16\n", " 0.2041241452319304\n", " 0.35355339059327373\n", " 0.4082482904638639" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "v2 = E.vectors[:,2]" ] }, { "cell_type": "code", "execution_count": 9, "id": "4d5f1cb4", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot(v2,marker=5,legend=false)\n", "xlabel!(\"vertex number\")\n", "ylabel!(\"value in eigenvector\")" ] }, { "cell_type": "code", "execution_count": 10, "id": "0664f854", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "plot(E.vectors[:,1],label=\"v1\",marker = 5)\n", "plot!(E.vectors[:,2],label=\"v2\",marker = 5)\n", "plot!(E.vectors[:,3],label=\"v3\",marker = 5)\n", "plot!(E.vectors[:,4],label=\"v4\",marker = 5)\n", "xlabel!(\"Vertex Number\")\n", "ylabel!(\"Value in Eigenvector\")" ] }, { "cell_type": "code", "execution_count": 11, "id": "6031c1b0", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Plots.plot(E.vectors[:,n],label=\"vn\",marker=5)\n", "xlabel!(\"Vertex Number\")\n", "ylabel!(\"Value in Eigenvector\")" ] }, { "cell_type": "code", "execution_count": 12, "id": "a8e080c1", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "V = E.vectors[:,2:3]\n", "plot_graph(M,V[:,1],V[:,2]);" ] }, { "cell_type": "code", "execution_count": 13, "id": "1d3b4df6", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "spectral_drawing(M);" ] }, { "cell_type": "markdown", "id": "5ed2ecb8", "metadata": {}, "source": [ "# Grid Graphs\n", "\n", "Commands for generating grids\n", "* n1xn2 2-d grid: grid2(n1,n2)\n", "* n1xn2xn3 3-d grid: grid3(n1,n2,n3)" ] }, { "cell_type": "code", "execution_count": 14, "id": "57260f32", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "36×2 Matrix{Float64}:\n", " -0.319588 0.0391375\n", " -0.282015 -0.00892256\n", " -0.216936 -0.092165\n", " -0.141789 -0.188285\n", " -0.0767107 -0.271528\n", " -0.0391375 -0.319588\n", " -0.271528 0.0767107\n", " -0.233954 0.0286506\n", " -0.168876 -0.0545918\n", " -0.0937294 -0.150712\n", " -0.0286506 -0.233954\n", " 0.00892256 -0.282015\n", " -0.188285 0.141789\n", " ⋮ \n", " -0.00892256 0.282015\n", " 0.0286506 0.233954\n", " 0.0937294 0.150712\n", " 0.168876 0.0545918\n", " 0.233954 -0.0286506\n", " 0.271528 -0.0767107\n", " 0.0391375 0.319588\n", " 0.0767107 0.271528\n", " 0.141789 0.188285\n", " 0.216936 0.092165\n", " 0.282015 0.00892256\n", " 0.319588 -0.0391375" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M = grid2(6,6)\n", "L = lap(M)\n", "E = eigen(Matrix(L))\n", "V = E.vectors[:,2:3]" ] }, { "cell_type": "code", "execution_count": 15, "id": "10c8d3bd", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plot_graph(M,V[:,1],V[:,2]);" ] }, { "cell_type": "code", "execution_count": 16, "id": "bafd34dd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "125-element Vector{Float64}:\n", " -1.2450300514738805e-15\n", " 0.381966011250105\n", " 0.38196601125010554\n", " 0.3819660112501058\n", " 0.7639320225002089\n", " 0.7639320225002092\n", " 0.7639320225002117\n", " 1.145898033750316\n", " 1.381966011250106\n", " 1.3819660112501062\n", " 1.381966011250107\n", " 1.7639320225002078\n", " 1.7639320225002098\n", " ⋮\n", " 7.618033988749906\n", " 7.854101966249687\n", " 8.618033988749897\n", " 8.618033988749902\n", " 8.618033988749906\n", " 8.854101966249669\n", " 8.854101966249685\n", " 8.854101966249685\n", " 9.854101966249683\n", " 9.854101966249686\n", " 9.854101966249688\n", " 10.854101966249683" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M = grid3(5,5,5)\n", "L = lap(M)\n", "E = eigen(Matrix(L))\n", "V = E.vectors[:,2:4]\n", "E.values" ] }, { "cell_type": "code", "execution_count": 17, "id": "b4a4d275", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plot_graph(M, V[:,1],V[:,2],V[:,3],setaxis=false);" ] }, { "cell_type": "code", "execution_count": 18, "id": "6b887659", "metadata": {}, "outputs": [ { "data": { "application/vnd.webio.node+json": { "children": [], "instanceArgs": { "namespace": "html", "tag": "div" }, "nodeType": "DOM", "props": {}, "type": "node" }, "text/html": [ "
The WebIO Jupyter extension was not detected. See the\n", "\n", " WebIO Jupyter integration documentation\n", "\n", "for more information.\n", "