Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast Adaptive Numerical Methods for High Frequency Waves and Interface Tracking
KTH, School of Computer Science and Communication (CSC), Numerical Analysis, NA (closed 2012-06-30).
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The main focus of this thesis is on fast numerical methods, where adaptivity is an important mechanism to lowering the methods' complexity. The application of the methods are in the areas of wireless communication, antenna design, radar signature computation, noise prediction, medical ultrasonography, crystal growth, flame propagation, wave propagation, seismology, geometrical optics and image processing.  

We first consider high frequency wave propagation problems with a variable speed function in one dimension, modeled by the Helmholtz equation. One significant difficulty of standard numerical methods for such problems is that the wave length is very short compared to the computational domain and many discretization points are needed to resolve the solution. The computational cost, thus grows algebraically with the frequency w. For scattering problems with impenetrable scatterer in homogeneous media, new methods have recently been derived with a provably lower cost in terms of w. In this thesis, we suggest and analyze a fast numerical method for the one dimensional Helmholtz equation with variable speed function (variable media) that is based on wave-splitting. The Helmholtz equation is split into two one-way wave equations which are then solved iteratively for a given tolerance. We show rigorously that the algorithm is convergent, and that the computational cost depends only weakly on the frequency for fixed accuracy. 

We next consider interface tracking problems where the interface moves by a velocity field that does not depend on the interface itself. We derive fast adaptive  numerical methods for such problems. Adaptivity makes methods robust in the sense that they can handle a large class of problems, including problems with expanding interface and problems where the interface has corners. They are based on a multiresolution representation of the interface, i.e. the interface is represented hierarchically by wavelet vectors corresponding to increasingly detailed meshes. The complexity of standard numerical methods for interface tracking, where the interface is described by marker points, is O(N/dt), where N is the number of marker points on the interface and dt is the time step. The methods that we develop in this thesis have O(dt^(-1)log N) computational cost for the same order of accuracy in dt. In the adaptive version, the cost is O(tol^(-1/p)log N), where tol is some given tolerance and p is the order of the numerical method for ordinary differential equations that is used for time advection of the interface.  

Finally, we consider time-dependent Hamilton-Jacobi equations with convex Hamiltonians. We suggest a numerical method that is computationally efficient and accurate. It is based on a reformulation of the equation as a front tracking problem, which is solved with the fast interface tracking methods together with a post-processing step.  The complexity of standard numerical methods for such problems is O(dt^(-(d+1))) in d dimensions, where dt is the time step. The complexity of our method is reduced to O(dt^(-d)|log dt|) or even to O(dt^(-d)).

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2012. , ix, 58 p.
Series
Trita-NA, ISSN 0348-2952 ; 2012:13
Keyword [en]
high frequency waves, Helmholtz equation, interface tracking, time-space adaptivity, multiresolution, Hamilton-Jacobi
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-105062ISBN: 978-91-7501-577-4 (print)OAI: oai:DiVA.org:kth-105062DiVA: diva2:568083
Public defence
2012-12-10, D2, Lindstedtsvägen 5, KTH, Stockholm, 10:15 (English)
Opponent
Supervisors
Funder
Swedish e‐Science Research Center
Note

QC 20121116

Available from: 2012-11-16 Created: 2012-11-15 Last updated: 2013-04-09Bibliographically approved
List of papers
1. Analysis of a fast method for solving the high frequency Helmholtz equation in one dimension
Open this publication in new window or tab >>Analysis of a fast method for solving the high frequency Helmholtz equation in one dimension
2011 (English)In: BIT Numerical Mathematics, ISSN 0006-3835, E-ISSN 1572-9125, Vol. 51, no 3, 721-755 p.Article in journal (Refereed) Published
Abstract [en]

We propose and analyze a fast method for computing the solution of the high frequency Helmholtz equation in a bounded one-dimensional domain with a variable wave speed function. The method is based on wave splitting. The Helmholtz equation is split into one-way wave equations with source functions which are solved iteratively for a given tolerance. The source functions depend on the wave speed function and on the solutions of the one-way wave equations from the previous iteration. The solution of the Helmholtz equation is then approximated by the sum of the one-way solutions at every iteration. To improve the computational cost, the source functions are thresholded and in the domain where they are equal to zero, the one-way wave equations are solved with geometrical optics with a computational cost independent of the frequency. Elsewhere, the equations are fully resolved with a Runge-Kutta method. We have been able to show rigorously in one dimension that the algorithm is convergent and that for fixed accuracy, the computational cost is asymptotically just for a pth order Runge-Kutta method, where omega is the frequency. Numerical experiments indicate that the growth rate of the computational cost is much slower than a direct method and can be close to the asymptotic rate.

Keyword
Helmholtz equation, High frequency, Wave splitting
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-40647 (URN)10.1007/s10543-011-0315-7 (DOI)000294463100013 ()2-s2.0-80052296077 (Scopus ID)
Funder
Swedish e‐Science Research Center
Note
QC 20110927Available from: 2011-09-27 Created: 2011-09-20 Last updated: 2017-12-08Bibliographically approved
2. Adaptive Fast Interface Tracking Methods: Part I: Time Adaptivity
Open this publication in new window or tab >>Adaptive Fast Interface Tracking Methods: Part I: Time Adaptivity
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper, we present a fast adaptive numerical method for interface tracking that uses an explicit multiresolution description of the interface. The interface is represented by wavelet vectors that correspond to the details of the interface on different scale levels.The complexity of standard numerical methods for interface tracking, where the interface is described by marker points, is O(N/dt), where N is the number of points on the interface and dt is the time step. The methods that we propose in this paper have O(tol^(-1/p)log N) computational cost, where tol is some given tolerance and p is the order of the numerical method for ordinary differential equations that is used for time advection of the interface. The adaptivity makes methods robust in the sense  that they can handle problems with both smooth and non-smooth interfaces (i.e. interfaces with corners) while keeping low computational cost.

Keyword
interface tracking, time adaptivity, multiresolution representation
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-105059 (URN)
Note

QS 2012

Available from: 2012-11-15 Created: 2012-11-15 Last updated: 2012-11-16Bibliographically approved
3. Adaptive Fast Interface Tracking Methods: Part II: Spatial Adaptivity
Open this publication in new window or tab >>Adaptive Fast Interface Tracking Methods: Part II: Spatial Adaptivity
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper, we present a fast space-time adaptive numerical method for interface propagation in a time varying velocity field based on a multiresolution description of the interface. The interface is represented by wavelet vectors that correspond to the details of the interface on different scale levels.The method is an extension of the method proposed in "J. Popovic and O. Runborg, Adaptive fast interface tracking methods: Part I, preprint (2012)", which is only time adaptive and it is thus not suitable for problems with expanding interfaces. The method that we propose in this paper, remedies that disadvantage of the time adaptive method in an efficient way. 

Keyword
interface tracking, time-space adaptivity, multiresolution representation
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-105060 (URN)
Note

QS 2012

Available from: 2012-11-15 Created: 2012-11-15 Last updated: 2012-11-16Bibliographically approved
4. Time Upscaling for Hamilton-Jacobi Equations
Open this publication in new window or tab >>Time Upscaling for Hamilton-Jacobi Equations
(English)Manuscript (preprint) (Other academic)
Abstract [en]

 In this paper, we suggest an accurate and computationally efficient numerical method for time-dependent Hamilton-Jacobi equations with convex Hamiltonians. The method is based on a reformulation of the Hamilton-Jacobi equation as a front tracking problem, which is solved with the fast interface tracking methods together with a post-processing step. The complexity of standard numerical methods for such problems is O(dt^(-(d+1))) in d dimensions, where dt is the time step. The complexity of the method that we propose in this paper is reduced to O(dt^(-d)|log dt|) or even to O(dt^(-d)).

Keyword
time upscaling, Hamilton-Jacobi
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-105061 (URN)
Note

QS 2012

Available from: 2012-11-15 Created: 2012-11-15 Last updated: 2012-11-16Bibliographically approved

Open Access in DiVA

fulltext(2334 kB)499 downloads
File information
File name FULLTEXT01.pdfFile size 2334 kBChecksum SHA-512
187583fe836211c9613da6db02aff940bc05557fe854b5005b5a0fdc426b4e7eec3f57f33459194c616bfcfd8a2a87314c29d69e7474b69d251b9900d8bd590c
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Popovic, Jelena
By organisation
Numerical Analysis, NA (closed 2012-06-30)
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 499 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 264 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf