Israel Pollak Distinguished Lectures by Gene H. Golub

Israel Pollak Distinguished Lectures by Gene H. GolubThe Israel Pollak distinguished lectures will be give this year by Professor Gene H. Golub from Stanford University. The first lecture, "A History of Numerical Linear Algebra", will be given on Tuesday, June 22, 2004 at 14:30. The second lecture, "Google Searches and Adaptive Methods for Updating/Downdating Page Ranks", will be given on Wednesday, June 23, 2004, at 14:30. Both lectures will take place in Auditorium 2 of Taub building.


A History of Numerical Linear Algebra

From the days of the first ballistic computations on digital computers, the vast majority of computer time used for scientific computation is spent on linear algebra problems. Pioneers like Lanczos, von Neumann, and Wilkinson led a revolution in advanced computing using machines like the ENIAC and ACE in the early and middle years of this century. We shall describe some pioneers in numerical linear algebra and their influence. Over the years, many effective techniques have been developed for solving scientific and engineering computing problems from ballistics to quantum mechanics. We shall discuss several of these problems in linear algebra and describe, in outline, their solution. Within the last decade, parallel and vector computers have sparked a new revolution with profound affects on numerical analysis. Some techniques banished as inferior for conventional computers have proved to be attractive alternatives for machines with advanced architectures. Supercomputer research has also led to improved algorithms for conventional serial computers as well. Finally, we shall discuss some of the latest advances, results, and current directions in scientific computation and numerical linear algebra.

Google Searches and Adaptive Methods for Updating/Downdating Page Ranks

Google's PageRank algorithm for web search involves computing the principal eigenvector of a stochastic matrix describing the hyperlink structure of the World Wide Web. Since the web is a highly dynamic structure, with new pages constantly being added or removed, the update problem is an important problem in web search. We address the problem of efficiently recomputing the principal eigenvector of the web hyperlink matrix after small perturbations in the link structure of the web. We present an algorithm that is motived by the empirical observation that the convergence patterns of web pages in the PageRank algorithm have a nonuniform distribution. Specifically, many pages converge to their true PageRank quickly, while relatively few pages take a much longer time to converge. This algorithm, called Adaptive PageRank, avoids redundant computations associated with the PageRanks of pages that have already converged. We show empirically that Adaptive PageRank speeds up the computation of PageRank even in the standard case, and that is is much more effective in the context of updates.

Back to the news index Saturday, June 12, 2004