One of the Baltimore Ravens Just Published an Insanely Complex Study in a Math Journal

From the original article:

In this paper, we introduce a new and fast coarsening algorithm, based on the conecpt of heavy edge matching, with a more aggressive coarsening procedure. For refinement, we implement a form of power iteration. For both our coarsening and refinement procedures we have created algorithms that are straightforward to implement. While heavy edge matching is complicated and tough to implement in high level programming languages, since it involves selecting an edge with heaviest weight between two unmatched vertices, heavy edge coarsening is significantly easier because we do not need to worry about whether a vertex has been aggregated or not. For the refinement procedure, power iteration does not require the inversion of a matrix, making its use much more straightforward than for Rayleigh quotient iteration, which requires some technique to approximately invert the matrix. Based on these two improved components, we propose a cascadic multigrid (CMG) method to compute the Fiedler vector.

He then goes on to say --- and this is what I find to be most amazing -- because he is so deadpan in the delivery:

As a model which shares a great deal of properties with the graph Laplacian eigenproblem, we consider the following elliptic eigenvalue problem with Neumann boundary conditions, − ∆ϕ = λϕ, on Ω, ∂ϕ ∂n = 0, on ∂Ω (3.1) where Ω ∈ R d is a polygonal Lipschitz domain. We only consider the two- and three- dimensional case to illustrate the theoretical bounds that can be obtained for the cascadic multilevel algorithm. However, the GCMG method we discussed here can be naturally applied for higher dimentional cases. Using the standard Sobolev space H1 (Ω), we consider the weak formulation of (3.1) as follows: find (λ, ϕ) ∈ R × H1 (Ω) such that a(ϕ, v) = λ(ϕ, v), ∀ v ∈ H1 (Ω), (3.2) where the bilinear form a(u, v) = (∇u, ∇v), and (·, ·) is the standard L 2 inner product. Here, the bounded symmetric bilinear form a(·, ·) is coercive on the quotient space H1 (Ω), and, therefore, induces an energynorm as follows: kuk 2 a = a(u, u), ∀ u ∈ H1 (Ω)\R. (3.3) Moreover, we denote the L 2 -norm by k · k as usual. Similar to the eigenvalues for the graph Laplacian, λ = 0 is also an eigenvalue of the eigenvalue problem (3.2), We can order the eigenvalues as follows: 0 = λ (1) ≤ λ (2) ≤ ... and denote by ϕ (1), ϕ(2) , ... the corresponding eigenfunctions. Again, we are interested in approximating the second smallest eigenvalue of (3.2) and its corresponding eigenfunction space. Given a nested family of quasi-uniform triangulations {Γj} J j=0, namely, 1 c 2 j−J ≤ hj = max T∈Γj diam(T ) ≤ c2 j−J , the spaces of linear finite elements are Vj = {u ∈ C(Ω) : u|T ∈ P1(T ), ∀ T ∈ Γj}, where P1(T ) denotes the linear functions on the triangle T . We have VJ ⊂ VJ−1 ⊂ · · · ⊂ V0 ⊂ H1 (Ω).

/r/news Thread Link -