DOC PREVIEW
UMD CMSC 878R - An FMM toolbox for MATLAB

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Group Project: An FMM toolbox for MATLABCMSC 878R/AMSC 698 R/ MAIT 627, Spring 2008Ramani Duraiswami and Nail GumerovApril 10, 2008AbstractThe goal of this project is to provide an FMM toolbox (publicly available) integrated in to Matlab.The goal is correctness and a full understanding of concepts. Five sub-projects are identified, and aschedule for the completion is given.1 IntroductionThe goal of this joint project is to create a collection of FMM-related functions that are tied in to MATLAB.The tasks are divided in to five pieces, and each task is assigned to a main person (responsible for coding), asecondary person (responsible for documentation/testing). Each student will have the role of a main personon one part and that of the secondary person on another part. Finally at the end of the project, eachstudent must build one example case using the overall code. This project will involve substantial work, andyou should plan on spending several hours on it weekly.The focus is on correctness and concepts, and prototyping. Some functions might also be converted into MEX form (with the native code written in Fortran or C).A piece of advice is to understand the calling of functions in Matlab, and how you can have variablearguments, variable function names, etc. Also since Matlab is organized column major as far as matrixstorage is concerned, your algorithms should respect this.You can share your comments, code and documentation via the following wiki page for the projecthttps://wiki.cs.umd.edu/Matlab_FMM. Create accounts for yourselves and post a test message. Weeklyreports also have to be posted here (and read by all of you).2 Project Pieces2.1 Data Structures and the Overall FMM AlgorithmThis follows closely from the homework on data structures, where you were asked to build a set of functions.You will build the same functions here as well. In the homework, the functions only had to work in 1-D.Here you have to make sure that the functions work in 1, 2 and 3-D.In addition you will build the overall FMM algorithm (upward pass, downward pass and final summation;skipping empty boxes). One piece of advice, is to keep the piece with the direct computations separate, sincethere are some opportunities for separate speed up of this piece.2.2 Translation OperatorsA package of S expansions, R expansions, S|S, S|R and R|R translations for various commonly used “FMM”-able functions in 1, 2 and 3-D will be built.This will be seeded by the 1-D Cauchy kernel we have been doing homework on.Later we will add the following1• 2D Laplace• 3D Laplace• 2D Helmholtz• Faster versions of the 2D/3D Laplace.The functions and expansions must be all tested and demonstrated.2.3 Adaptive Versions of the FMMAdaptive versions of the FMM are discussed in two papers. Cheng et al. in the Journal of ComputationalPhysics, and in a chapter in our book. There are also two Java implementations of adaptive FMM in 2D,as previous course projects. Running the adaptive version also changes the running of the overall FMMalgorithm since the downward pass can be substantially modified.2.4 Using the FMM with Matlab RoutinesThe FMM is mainly used in application problems, including the following1. Time dependent inter particle computations (e.g. in stellar dynamics, molecular dynamics, vortexelement methods)2. Dense linear system solutions (e.g., in function fitting, boundary element methods, equivalent sourcemethods etc.). For such problems source and evaluation points are the same.3. Eigen value problems (e.g., stability computations, acoustics, etc.)2.4.1 Existing Matlab Routines and the FMMThus it would be useful to use the rich Matlab environment and implement some test applications. ManyMatlab routines allow a user defined routine for matrix vector products. These include the following• pcg: Preconditioned conjugate gradient• gmres: Preconditioned generalized minimum residual solution of a linear system (usually non-symmetric).• eigs: Determining a few eigenvalues and eigenvectorsThere are several others that could also be called.In addition, while the routine condest and normest do not provide a matrix-vector function call link,they also rely on mat-vecs.The goal is to use the FMM with these.2.4.2 Time IntegratorsIn addition we can compute particle dynamics via the FMM using some standard integrators. Standardintegrators will have the formddtx1x2...xn=f1(x1, · · · , xn, t)f2(x1, · · · , xn, t)...fn(x1, · · · , xn, t)Incorporate the FMM in to a simple Euler computation of N-body calculations in 2D, and then extendit to higher order integrators.22.4.3 PreconditioningPreconditioning is important in many computations for fast convergence. A particularly simple precondi-tioner may be appropriate to use with the FMM, and is described here. Consider a matrix Φ. Its inverse canbe computed by solving N linear systems with the right hand sides of these systems being formed by thecolumns of the identity matrix. If each of the solution vectors are stacked as the columns of a matrix, thismatrix is the inverse. Now, as discussed in class the best preconditioner is the inverse, but it is too expensiveto compute. The best practical preconditioners are approximate inverses that are inexpensive to compute.Each row of the matrix in a FMM matrix vector product can be associated with a single evaluation point(and for a linear system solution, that source point). The idea of the preconditioner is to take a small groupof q points (e.g., the points we do direct evaluation with, plus some close by points), and solve a small linearsystem, at O(q3) cost We do this for all N points, and create an approximate inverse matrix by extendingthe q vector to a N vector by adding zeroes at the locations not considered. Stacking these columns, we havein principle an approximate preconditioner, which requires O(N q) storage. To apply this preconditioner ittakes O(q2N) operations.We will try out this precondtioner, and we can use the conditione estimator to check how much thecondition number improves..2.5 Use of the Improved Fast Gauss TransformThe improved fast Gauss transform code is available on sourceforge and computes the gaussian sum. Thegoal is to build a Matlab interface to this package.3 ScheduleSelection of pieces: April 10General Matlab Framework: All: April 15Implemented 1-D Framework: All: April 17Familiarization


View Full Document

UMD CMSC 878R - An FMM toolbox for MATLAB

Download An FMM toolbox for MATLAB
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view An FMM toolbox for MATLAB and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view An FMM toolbox for MATLAB 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?