There has been a rise in the popularity of algebraic methods for graph
algorithms given the development of the GraphBLAS library and other sparse
matrix methods. An exemplar for these approaches is Breadth-First Search (BFS).
The algebraic BFS algorithm is simply a recurrence of matrix-vector
multiplications with the $n \times n$ adjacency matrix, but the many redundant
operations over nonzeros ultimately lead to suboptimal performance. Therefore
an optimal algebraic BFS should be of keen interest especially if it is easily
integrated with existing matrix methods.
Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse
Vector (SpMmSpV) multiplication in which the input vector is kept in a sparse
representation in each step of the BFS, and nonzeros in the vector are masked
in subsequent steps. This has been an area of recent research in GraphBLAS and
other libraries. While in theory these masking methods are asymptotically
optimal on sparse graphs, many add work that leads to suboptimal runtime. We
give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the
literature.
Our method multiplies progressively smaller submatrices of the adjacency
matrix at each step. Let $n$ and $m$ refer to the number of vertices and edges,
respectively. On a sparse graph, our method takes $O(n)$ algebraic operations
as opposed to $O(m)$ operations needed by theoretically optimal sparse matrix
approaches. Thus for sparse graphs it matches the bounds of the best-known
sequential algorithm and on a Parallel Random Access Machine (PRAM) it is
work-optimal. Our result holds for both directed and undirected graphs.
Compared to a leading GraphBLAS library our method achieves up to 24x faster
sequential time and for parallel computation it can be 17x faster on large
graphs and 12x faster on large-diameter graphs.

我们给出了一种基于代数方法的新的最佳优化 BFS 算法，使用渐进的小子矩阵乘法还原了图的结构，对于稀疏图性能与最优算法保持一致，并且在 PRAM 上是工作最优的。

稀疏图的最优代数广度优先搜索

Optimal algebraic Breadth-First Search for sparse graphs

The problem of principle component analysis (PCA) is traditionally solved by
spectral or algebraic methods. We show how computing the leading principal
component could be reduced to solving a \textit{small} number of
well-conditioned {\it convex} optimization problems. This gives rise to a new
efficient method for PCA based on recent advances in stochastic methods for
convex optimization.
In particular we show that given a $d\times d$ matrix $\X =
\frac{1}{n}\sum_{i=1}^n\x_i\x_i^{\top}$ with top eigenvector $\u$ and top
eigenvalue $\lambda_1$ it is possible to: \begin{itemize} \item compute a unit
vector $\w$ such that $(\w^{\top}\u)^2 \geq 1-\epsilon$ in
$\tilde{O}\left({\frac{d}{\delta^2}+N}\right)$ time, where $\delta = \lambda_1
- \lambda_2$ and $N$ is the total number of non-zero entries in
$\x_1,...,\x_n$,
\item compute a unit vector $\w$ such that $\w^{\top}\X\w \geq
\lambda_1-\epsilon$ in $\tilde{O}(d/\epsilon^2)$ time. \end{itemize} To the
best of our knowledge, these bounds are the fastest to date for a wide regime
of parameters. These results could be further accelerated when $\delta$ (in the
first case) and $\epsilon$ (in the second case) are smaller than $\sqrt{d/N}$.

本文介绍了一种基于凸优化和随机方法的新的高效 PCA 方法，该方法能够在很短的时间内计算出一个给定矩阵的主成分，并且在一定参数范围内实现了迄今最快的计算速度。

通过凸优化实现快速简易的 PCA

Fast and Simple PCA via Convex Optimization

In the constraint satisfaction problem ($CSP$), the aim is to find an
assignment of values to a set of variables subject to specified constraints. In
the minimum cost homomorphism problem ($MinHom$), one is additionally given
weights $c_{va}$ for every variable $v$ and value $a$, and the aim is to find
an assignment $f$ to the variables that minimizes $\sum_{v} c_{vf(v)}$. Let
$MinHom(\Gamma)$ denote the $MinHom$ problem parameterized by the set of
predicates allowed for constraints. $MinHom(\Gamma)$ is related to many
well-studied combinatorial optimization problems, and concrete applications can
be found in, for instance, defence logistics and machine learning. We show that
$MinHom(\Gamma)$ can be studied by using algebraic methods similar to those
used for CSPs. With the aid of algebraic techniques, we classify the
computational complexity of $MinHom(\Gamma)$ for all choices of $\Gamma$. Our
result settles a general dichotomy conjecture previously resolved only for
certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of
Combinatorics, 2008].

本文研究了约束满足问题和最小代价同构问题，并通过代数方法对最小代价同构问题进行了分类以解决其计算复杂度，并将其应用于许多组合优化问题中。