lapackers

[Ming Gu <mgu@math.berkeley.edu>]

               Math 290, Section 29, CS 298, Section 6,
                          Spring 2011
         (Matrix Computations and Scientific Computing)

We meet WEDNESDAYS 11:10 - noon in Room 380 Soda Hall,
Berkeley campus.  The coordinators are Profs. J. Demmel
(demmel@cs.berkeley.edu) and M. Gu (mgu@math.berkeley.edu).
The program will be a mixture of research talks and
tutorials.  The tutorials will provide a partial sequel to
Math 221.

For the schedule and other details about the seminar, please see
math.berkeley.edu/~mgu/LAPACKSeminar.htm

Date: Feb. 2
Speaker:Dr. David Gleich 
Title: Fast Katz and Commuters - Quadrature Rules and Sparse
  Linear Solvers for Link Prediction Heuristics

Abstract: Motivated by social network data mining problems
such as link prediction and collaborative filtering,
significant research effort has been devoted to computing
topological measures including the Katz score and the
commute time. Existing approaches approximate all pairwise
relationships simultaneously. We are interested in
computing he score for a single pair of nodes; e top-k
nodes with the best scores from a given source node.

For the pairwise problem, we introduce an iterative
algorithm that computes upper and lower bounds for the
measures we seek. This algorithm exploits a relationship
between the Lanczos process and a quadrature rule.

For the top-k problem, we propose an algorithm that only
accesses a small portion of the graph, similar to algorithms
used in personalized PageRank computing. To test scalability
and accuracy, we experiment with three real-world networks
and find that our algorithms run in milliseconds to seconds
without any preprocessing.

Date: Feb. 9 
Speaker: Jim Demmel