Series:

Applied and Computational Mathematics Seminar

Thursday, April 23, 2009 - 1:00pm

1 hour (actually 50 minutes)

Location:

Skiles 255

Organizer:

Note special day

Linear boundary value problems occur ubiquitously in many areas of

science and engineering, and the cost of computing approximate

solutions to such equations is often what determines which problems

can, and which cannot, be modelled computationally. Due to advances in

the last few decades (multigrid, FFT, fast multipole methods, etc), we

today have at our disposal numerical methods for most linear boundary

value problems that are "fast" in the sense that their computational

cost grows almost linearly with problem size. Most existing "fast"

schemes are based on iterative techniques in which a sequence of

incrementally more accurate solutions is constructed. In contrast, we

propose the use of recently developed methods that are capable of

directly inverting large systems of linear equations in almost linear

time. Such "fast direct methods" have several advantages over

existing iterative methods:

(1) Dramatic speed-ups in applications involving the repeated solution

of similar problems (e.g. optimal design, molecular dynamics).

(2) The ability to solve inherently ill-conditioned problems (such as

scattering problems) without the use of custom designed preconditioners.

(3) The ability to construct spectral decompositions of differential

and integral operators.

(4) Improved robustness and stability.

In the talk, we will also describe how randomized sampling can be used

to rapidly and accurately construct low rank approximations to matrices.

The cost of constructing a rank k approximation to an m x n matrix A

for which an O(m+n) matrix-vector multiplication scheme is available

is O((m+n)*k). This cost is the same as that of the well-established

Lanczos scheme, but the randomized scheme is significantly more robust.

For a general matrix A, the cost of the randomized scheme is O(m*n*log(k)),

which should be compared to the O(m*n*k) cost of existing deterministic

methods.

science and engineering, and the cost of computing approximate

solutions to such equations is often what determines which problems

can, and which cannot, be modelled computationally. Due to advances in

the last few decades (multigrid, FFT, fast multipole methods, etc), we

today have at our disposal numerical methods for most linear boundary

value problems that are "fast" in the sense that their computational

cost grows almost linearly with problem size. Most existing "fast"

schemes are based on iterative techniques in which a sequence of

incrementally more accurate solutions is constructed. In contrast, we

propose the use of recently developed methods that are capable of

directly inverting large systems of linear equations in almost linear

time. Such "fast direct methods" have several advantages over

existing iterative methods:

(1) Dramatic speed-ups in applications involving the repeated solution

of similar problems (e.g. optimal design, molecular dynamics).

(2) The ability to solve inherently ill-conditioned problems (such as

scattering problems) without the use of custom designed preconditioners.

(3) The ability to construct spectral decompositions of differential

and integral operators.

(4) Improved robustness and stability.

In the talk, we will also describe how randomized sampling can be used

to rapidly and accurately construct low rank approximations to matrices.

The cost of constructing a rank k approximation to an m x n matrix A

for which an O(m+n) matrix-vector multiplication scheme is available

is O((m+n)*k). This cost is the same as that of the well-established

Lanczos scheme, but the randomized scheme is significantly more robust.

For a general matrix A, the cost of the randomized scheme is O(m*n*log(k)),

which should be compared to the O(m*n*k) cost of existing deterministic

methods.