course website: http://www.cse.uiuc.edu/courses/cs591mh/

2008-04-30

• Chronopoulus and Gear 1989
• de Sturler
• Demmel Hoemelman 2007-Present

2008-03-26

Spectruw, a black-box spectrum approximator?

• Firat Kiyak
• http://www.amath.washington.edu/hill/spectruw.html

2008-03-03

Data Parallel Abstractions for Irregular Applications

• big debate: program = algorithm + data structures. This speaker agrees, Bill disagrees.

Big idea:

• work queues, ordered and unordered.
• speculative execution, allow rollbacks.
• model work queues by sets and ordered sets that can be updated during the iteration.
• asks programmers to write their own inverse operations for modifications to shared objects
• uses Kale's virtual processor stuff.

Gene Golub symposium, 2008-02-29

Precondtioned Itertive Methods for Sequences of Linear systems

Eric de Sturler

Inverse Eigenvalue Problem

• generate a matrix with some spectral data. Chu and Golub, Theory, Algorithms and Applications.

references:

• finite element model updating in structural dynamics
• inverse problems in mechanical systems and signal processing.

Parallel Schemes for Solving Linear systems of Equations

Ahmed Sameh

asserts that lots of matrices can be permuted into banded structures

interested in banded preconditioners, wants to turn them into the black box preconditioner.

wants a preconditioner that can be scaled from direct to iterative, depending on the problem.

assertion: minimizing memory references, IPC, more important than minimizing computation.

Software: Spike

A New Approach to Affine Parametric Quadratic Inverse Eigenvalue Problem

Vadim Sokolov

%$ P(\lambda) = \lambda^2 M + \lambda C + K $%

Preconditioning with Selective Sparse Approximate Inversion

Padma Raghavan

Tree based methods.

• Drop Threshold Incomplete Cholesky with Selective Sparse Approximate
• Interesting, wants to make a direct/iterative hybrid.
• Asserts that the latency is O((log p)^2) for tree based methods.
• uses something like domain decomposition on the matrix, tries to assert that only certain processors can talk to each other at the time

Linear Algebra in the Analysis of Metabolic pathways

Daniel Boley

stoichiometry problem for finding elementary and extreme pathways.

Goal: figure out which pathways to modify to change cell output.

Notable people: shuster, Palsson

The Backward Analysis Dogma

Bob Skeel

• problem: %$ y = f(x) $%,
• forward error %$ g(x) - f(x) $%
• Backward error %$ g(x) - f(x) \approx f'(x) \delta x $%

Facts:

• there is no stable algorithm for inv(A)
• But there is a stable algorithm for kth col of inv(A), is this an artifact of the definition of stabilty

Proposes stability instead of backwards stability.

Petsc!

Bill

Note to self, when I grow up, I will make good slides.

Accuracy of Molecular Dynamics Simulation

I didn't understand any of this

2008-02-27

Dick Varga, matrix iterative methods - used to be the guide in the field

2008-02-06

Preconditioners for block Broyden Method

• Peng Jiang

Block Broyden used for solving large nonlinear systems

• http://www.cs.uiuc.edu/homes/pjiang2/publications/2.pdf

2007-11-08

General strength of connection measure.

• Jacob Schroder

2007-11-01

Nonnegative Matrix Factorizations

• Michael Turnley

Relation to data mining?

• sparse matrix, words by documents.

2007-10-25

Benchmarking Sparse Matrix Vector multiply

• HPCC HPCC Suite = LINPACK + FFT, matrix transpose, no sparse matrix vector multiply.

Three cases for Matrix vector multiply

• Small: everything fits in the cache
• Medium: source vector fits in the cache, matrix does not
• large: source vector does not fit in the cache.

University of Florida Sparse Matrix Collection - Tim Davis runs it.

OSKI - sparse matrix tuning for sparse matrix computations.

2007-10-03

Fast methods for the generalized possion equation

• Mitya

Multi-summation methods

2007-09-20

Numerical computation of Free Energies

• Eric Cyr

Free Energy: macroscopic property, energy of chemical reactions? Average energy in fine degrees of freedom in a coarse grained system.

Mistake on slide 18

2007-09-13

AMG for a Peta-scale Navier Stokes Code

• James Lottes

• SAI-0 shown to be a better dampener that weighted jacobi, always

M_{ii} = \frac {A_{ii}}{\sum_{i=1}^n A_{ik}A_{ik}}

%$ R_f AQR^T_f - A_{ff}$% versus %$ I-SMS^T A_{ff} $%

energy minimization of wan, chan, and smith

Partitioning for Paralle Spare Matrix Vector Multiplication.

• Michael Wolf

2007-09-06

Krylov subspace methods for topology optimation in adaptive mesh refinement

• Shaun Weng

Idea: cut out stuff from structures, keep maximum strength

• repeat until converged
  • do FEM
  • compute sensitivity
  • update density

Doing FEM over and over is hard, reuse old solutions

Use AMR to compute things in void, save work. Must get same result as in uniform case

• lookup GCRODR

Idea: has there ever been any quantification of effort versus speed of the application? IF one implementation takes 10 times as long to code but only gives a 50% speed up, then those researchers are being irresponsible.

2007-04-03

• efficient setup algorithms for parallel algebraic multigrid
• david alber

2007-02-27

• what: Gaussian elimination

• Now that computers are faster, some Strosden methods are better asymptoticly better for matrix multiplication. David Bailey has a fast matrix mult library that has seen positive performance improvements.
• LR iteration for eigenvaules, uses elementary elimination matricies.
• lesile foster , steve write - have examples of matrices where GE becomes unstable (with partial pivoting), stiff odes and dense programming.
• steve vavassas, gaussian elimination is not scalable (pivot sesarch kills)

• jhonseb and micheal turnley

2007-02-06

2007-01-30

• who: Heath
• what: who invented the great numerical algorithms?

2007-01-23

http://www.cse.uiuc.edu/courses/cs591mh/

list of papers on the class website.

2006-12-05

• Micheal heath
• cake cutting algorithms

• canonical problem of fair division.
  • fair: each player feels he'she recieves 1/n of cake
  • envy free: no player feels another player recieves a larger portion.
  • cut and choose - A divides cake, B selects piece, remaining piece goes to A.
    • fair, envy free.
  • trimming -
    • a pick 1/3
    • b trims to 1/3 if it's too big
    • c is offered piece,
      • if he rejects, b takes trimmed or a takes untrimmed.

2006-11-28

• Langevin equation - brownian motion
• Michael Turnley
• mq'' = -gradV(q)+R(t)-gamma*mq'
  • R is random *

2006-10-31

• Jehanzeb Hameed Chaudhry
• Work @ Microsoft
• worked on instruction virtualization.
• fixed some small bugs in the JIT
  • using "sealed" aka final classes should make dynamic runtime casting easier. He implemented this optimization
  • fixed a bug with array access in JIT versus machine code
  • wrote a profiler to see when compiled CLI fails.
• Process explorer - procexp.exe - lets you look at the program and all it's allocation resources.

2006-10-17

• michael wolf
• minimizing operations in matrix vector multiplication
• Dr. Kirby from chicago / texas tech
• look at local stiffness term for an element
  • use chain rule to separate reference element stuff from reference stuff
  • look at how they multiply, suggest frobneus product
  • remove esy products, then create a graph
  • add appropriate edge lengths, find minimum spanning tree
• above technique fail for linear combinations, need hypergraphs to get to the next level
  • why instead of generating intermediate nodes?
• turns into integer programming
  • might be NP hard, unproven

2006-10-10

• Eric syr
• poisson boltzman equation

• motivation: average the interactions at the molecular level.
• get strange terms: div(e(r)grad(u)) - K(r)*sinh(u)=sum of charges

2006-10-03

• jacob Schoder
• a better strencth of connection messure in amg

• lookup jacobi or gauss siedel for reduciton of matricies

2006-09-26

• Trillion Dollar Game
• Shun Wang

• derivatives in economics- an agreement that a trde is carried out at an agreed price K and at some future time T
  • straddle
    • \/
  • strangle
    • \_/
  • risk reversal
    • /-/
  • barrier
    • _/|
• futures - ??
• options - right to buy/sell some underlying asset at a predetermined price K at or within furture time T
  • auto insurance. Similar to a barrier?
• Arbitrage
  • same stock traded in different exhanges
  • buy cheap in one exchange, sell in another.
• Black-Scholes - differential equation to price options
  • stock follows brownian motion == random walk
  • no arbitrage
  • constant risk free interest rate
  • can trade continuously

2006-09-19

• multi scale analysis of turbulence in active regions using wavelets
• russel hewett

• turbulence
  • energy in turb systems scales E(k) ~ k^-alpha

2006-09-12

• Vulnerability Analysis of the Electric Power Grid
• Adam Reichert