Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

Tuesdays and Thursday, 10:30am-11:45am

CIVL 2123

In-class quiz 6 and solution

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

CS 59000-NMC, 8 September

Please answer the following questions. You may not use any outside references or technology. Justify and explain all answers. This quiz is for my own evaluation, so that I can provide better instruction in the course.

Question

Consider the following matrix-based algorithm for breadth-first search

Input: 
  A - adjacency matrix
  v - starting vertex

d(i) <- Inf for 1 <= i <= n
x <- e_v % i.e. x is a vector of all zeros with a 1 in the $v$th's position

for step = 1 to n
  y = A*x % do a mat-vec
  newv = {i : y(i) != 0 && d(i) == Inf } % set of newly found vertices
  d(newv) <- step % assign the current distance
  x <- x | y % set x 
  if |newv| == 0 then quit

What is the best bound you can put on the runtime of the algorithm, using any graph property you wish?

Solution

First, each iteration of the for-loop takes $O(|V| + |E|)$ work because a mat-vec is $O(|E|)$ work and the other operations take $O(|V|)$ work. Consequently, the question is really asking how many iterations the algorithm will perform. The best bound for this would be the eccentricity of the starting vertex $v$. Eccentricity is the longest-shortest path from a given vertex to any other vertex. The diameter of the graph is the largest eccentricity of any vertex. Hence, ignoring the identity of the starting vertex, the algorithm could run for diameter iterations.

The runtime is then bounded by $O(d \cdot (|V| + |E|))$ where $d$ is the diameter.

Here are a few special cases for the runtime

Chain graph

Suppose your graph is just a chain of n connected vertices. Then the diameter is n, and each iteration of the loop takes O(n) work, for a total runtime of O(n^2).

Clique graph

Suppose your graph is a clique, then there are n^2 edges, but the diameter is 1.

Clique and chain graph

Suppose the graph is a clique on $n/2$ vertices, and a single chain of $n/2$ vertices. Then there are $O(n^2)$ edges and a diameter of $O(n)$. Yielding a runtime of $O(n^3)$.

Specializing the algorithm.

A number of students tried to optimize the algorithm by using additional properties to get back to the standard $O(|V| + |E|)$ runtime. e.g. changing the algorithm so that x = e_newv, or just the non-zeros for the new set of vertices, and then using a sparse-matrix-sparse-vector product A*x will do this. This was greatly insightful, but was a bit outside the scope of the answers. Such thinking will be the core of how to do the forthcoming local algorithms, however.