xxxxxxxxxx
## CSS.205.1 Toolkit for TCS 2023 - Spectral Methods
xxxxxxxxxx
Jupyter Notebook for Spectral Methods module of course using the tools developed by Dan Spielman. References and sources:
* <a href="http://www.cs.yale.edu/homes/spielman/462/462schedule.html">Dan Spielman's course on Spectral Methods @ Yale University, 2019</a>.
* <a href="https://github.com/danspielman/Laplacians.jl">Laplacians Package</a> (by Dan Spielman)
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
Using Pkg
Pkg.add("Laplacians")
### Table of Contents
1. <a href="#Line-Graphs">Line Graphs</a>
2. <a href="#Grid-Graphs">Grid Graphs</a>
3. <a href="#Platonic-Solids">Platonic Solids</a>
Jupyter Notebook for Spectral Methods module of course using the tools developed by Dan Spielman. References and sources:
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
Using Pkg Pkg.add("Laplacians")
xxxxxxxxxx
using Laplacians
using LinearAlgebra
using Plots
using SparseArrays
using FileIO
using JLD2
using Random
xxxxxxxxxx
gr()
xxxxxxxxxx
# Paths / Cycles
Commands for generating path and cycles
* line: path_graph(#vertices)
* cycle: ring_graph(#vertices)
* Complete Bipartite graph on (n,n) vertices: complete_bipartite_graph(n)
* Star Graph: star_graph(#vertices)
Commands for generating path and cycles
xxxxxxxxxx
n=12
M = ring_graph(n)
xxxxxxxxxx
Matrix(M)
xxxxxxxxxx
L=Matrix(lap(M))
xxxxxxxxxx
E = eigen(Matrix(L))
println(E.values)
xxxxxxxxxx
E.vectors[:,1]
xxxxxxxxxx
v2 = E.vectors[:,2]
xxxxxxxxxx
plot(v2,marker=5,legend=false)
xlabel!("vertex number")
ylabel!("value in eigenvector")
xxxxxxxxxx
plot(E.vectors[:,1],label="v1",marker = 5)
plot!(E.vectors[:,2],label="v2",marker = 5)
plot!(E.vectors[:,3],label="v3",marker = 5)
plot!(E.vectors[:,4],label="v4",marker = 5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
xxxxxxxxxx
Plots.plot(E.vectors[:,n],label="vn",marker=5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
xxxxxxxxxx
V = E.vectors[:,2:3]
plot_graph(M,V[:,1],V[:,2]);
xxxxxxxxxx
spectral_drawing(M);
xxxxxxxxxx
# Grid Graphs
Commands for generating grids
* n1xn2 2-d grid: grid2(n1,n2)
* n1xn2xn3 3-d grid: grid3(n1,n2,n3)
Commands for generating grids
xxxxxxxxxx
M = grid2(6,6)
L = lap(M)
E = eigen(Matrix(L))
V = E.vectors[:,2:3]
xxxxxxxxxx
plot_graph(M,V[:,1],V[:,2]);
xxxxxxxxxx
M = grid3(5,5,5)
L = lap(M)
E = eigen(Matrix(L))
V = E.vectors[:,2:4]
E.values
xxxxxxxxxx
plot_graph(M, V[:,1],V[:,2],V[:,3],setaxis=false);
plotlyjs()
plot_graph(M, V[:,1],V[:,2],V[:,3]; setaxis=false);
xxxxxxxxxx
# Platonic Solids (https://en.wikipedia.org/wiki/Platonic_solid)
* Tetrahedron (https://en.wikipedia.org/wiki/Tetrahedron): tetra.txt
* Cube (https://en.wikipedia.org/wiki/Cube): cube.txt
* Dodecahedron (https://en.wikipedia.org/wiki/Dodecahedron): dodec.txt
* Icosahedron (https://en.wikipedia.org/wiki/Icosahedron): icosa.txt
* Octahedron (https://en.wikipedia.org/wiki/Octahedron): octa.txt
M = read_graph("icosa.txt")
xxxxxxxxxx
spectral_drawing(M);
xxxxxxxxxx
E = eigen(Matrix(lap(M)))
println(E.values)
xxxxxxxxxx
x = E.vectors[:,2]
y = E.vectors[:,3]
z = E.vectors[:,4]
plot_graph(M, x, y);
plot_graph(M, x, y, z; setaxis=false);
xxxxxxxxxx
n = length(E.values)
x = E.vectors[:,n-1]
y = E.vectors[:,n]
plot_graph(M, x, y; setaxis=false);
x = E.vectors[:,n]
y = E.vectors[:,n-1]
z = E.vectors[:,n-2]
plot_graph(M, x, y, z; setaxis=false);