posts

During my time at Lawrence Livermore National Laboratory, I worked on multilevel coarsening of graph laplacian problems. A paper detailing the project can be found at https://arxiv.org/abs/2003.04423. The implementation, GAUSS, uses my linear algebra library linalgcpp.

This post is a basic introduction to the Vector structure in linalgcpp.

In this example, we define an operator that computes the action of a Kernel Matrix without assembling the entire matrix. More precisely, each entry \(a_{i,j}\) in the matrix \(A\) is computed as \(K(x_i,x_j)\). Where \(K\) is some given kernel and \(x_i\) comes from some given dataset. This is often useful in machine learning when using the “kernel trick” in SVMs.

The power method is one of the simplest methods to find the maximum eigenpair of an operator. We simply compute \(x_{k+1}=\frac{Ax_k}{\left\lVert Ax_k \right\rVert}\) until the corresponding Rayleigh quotient \(\frac{x^TAx}{x^Tx}\) stops changing.

In practice it is often useful to check whether an operator is symmetric. The naive approach to check if a matrix is symmetric would be to verify that each element \(a_{ij}\) is equal to the element \(a_{ji}\) for all pair of indices \(i\) and \(j\) . However, for general operators, it is often the case that there is no direct access to the elements. Only the action is available.