International Journal of Discrete Mathematics
Volume 2, Issue 1, March 2017, Pages: 10-16

Wavelet-Based Numerical Homogenization for Scaled Solutions of Linear Matrix Equations

J. B. Allen

Information Technology Laboratory, U.S. Army Engineer Research and Development Center, Vicksburg, USA

Email address:

To cite this article:

J. B. Allen. Wavelet-Based Numerical Homogenization for Scaled Solutions of Linear Matrix Equations. International Journal of Discrete Mathematics. Vol. 2, No. 1, 2017, pp. 10-16. doi: 10.11648/j.dmath.20170201.13

Received: January 6, 2017; Accepted: January 20, 2017; Published: February 20, 2017


Abstract: In this work we investigate the use of wavelet-based numerical homogenization for the solution of various closed form ordinary and partial differential equations, with increasing levels of complexity. In particular, we investigate exact and homogenized (scaled) solutions of the one dimensional Elliptic equation, the two-dimensional Laplace equation, and the two-dimensional Helmholtz equation. For the exact solutions, we utilize a standard Finite Difference approach with Gaussian elimination, while for the homogenized solutions, we applied the wavelet-based numerical homogenization method (incorporating the Haar wavelet basis), and the Schur complement) to arrive at progressive coarse scale solutions. The findings from this work showed that the use of the wavelet-based numerical homogenization with various closed form, linear matrix equations of the type:  affords homogenized scale dependent solutions that can be used to complement multi-resolution analysis, and second, the use of the Schur complement obviates the need to have an a priori exact solution, while the possession of the latter offers the use of simple projection operations.

Keywords: Numerical Homogenization, Multiscale, Multiresolution, Wavelets


1. Introduction

Applications requiring multiscale characterization are becoming increasingly more numerous. This has been motivated by several inter-related factors, including, but not limited to; increased performance of enabling technologies (i.e., high performance computing capabilities), the confluence of increasingly more scale dependent fields of research, and requirements associated with making macroscale decisions based on nano or micro scale performance criteria.

In some instances one may be interested in finding coarse scale features independent of the finer scales. In such cases, the fine scale features may deemed of lesser importance, or may be computationally prohibitive. In other cases, the fine scales may not be ignored; they may contribute to the coarse scale solution.

Existing methods of multiscale modeling and simulation include: Fourier analysis [1], multigrid methods [2,3], domain decomposition methods [4,5], fast multipole methods [6], adaptive mesh refinement methods [7], wavelet-based methods [8], homogenization methods [9-13], quasi-continuum methods [14, 15], and others. Of these, wavelet-based methods, particularly those incorporating Multi-Resolution Analysis (MRA), have received special attention recently, mainly due to their inherent capacity to simultaneously represent multidimensional data as functions of both time and scale.

Conceived originally by Meyer [16] and Mallat [17] and founded on the principle of orthonormal, compactly supported wavelet bases functions; MRA is a rapidly developing field supporting an increasing number of scientific disciplines, including applied mathematics and signal analysis. One of the first successful applications of wavelet-based MRA was conducted by Basdevant et al. [18], in which continuous and discrete wavelet transforms and orthonormal wavelet decompositions were used to analyze coherent vortices in two-dimensional turbulent flows and the manner in which they contribute to the energy distribution. Their findings indicated that the wavelet coefficients, along with local spectra and local enstrophy fluxes were powerful tools that could be used to separate the different dynamical behaviors attributable to the various scales of the flow.

Complementary to wavelet-based multi-resolution theory, and founded on the same underlying theoretical principles, wavelet-based numerical homogenization has also shown unique potential, particularly among applications involving scale dependent solutions of various closed form, linear matrix equations; i.e., those encountered within Finite Element, Finite Difference or Finite Volume formulations.

In this paper we intend to augment the existing numerical homogenization research portfolio [9-13], and investigate the use of wavelet-based numerical homogenization for the solution of various closed form ordinary and partial differential equations, with increasing levels of complexity. In particular, we will investigate exact and homogenized (scaled) solutions of the one dimensional Elliptic equation, and the two-dimensional Laplace and Helmholtz equations.

2. Method

Although the theory and background ascribed to wavelet-based multiresolution analysis and numerical homogenization has been well described in other works [9-13], in this section, for purposes of completeness, we will provide an overview of each process.

2.1. Wavelet-based Multiresolution Analysis

In this section, the filtering procedure for splitting a function into high and low scale components is provided. In this context, two related functions are defined, namely; the scaling function (x), comprising the low-pass, "smoothing" filtering operation, and the wavelet function , providing detailed, high-pass support. By definition, a multiresolution analysis may be characterized by a nested sequence of closed subspaces , each identifiable by a given scaling parameter, r, and with the following properties:

(1)

(2)

(3)

Further, each subspace , is spanned by a unique set of scaling functions , such that:

(4)

Where s is defined as the shift or translation parameter.

A mutually orthogonal complement of  in  is denoted by a subspace , such that:

(5)

where  is the direct summation. Nearly identical to , the subspace  is spanned by a set of orthogonal basis functions of the form:

(6)

Where the wavelet function,  is translationally orthogonal to the scaling function. Using Eqs. (2) and (8), we have:

(7)

It follows that:

(8)

The functions  in Equation 4 generate an  orthogonal basis that is orthogonal under translation. We note that for a fixed r,  spans the entire  function space and thus any function, f can be approximated from the  basis:

(9)

Where  is the operator projecting f onto the subspace  spanned by . For example, the scaling function, can be written as:

(10)

Where  is the scaling function coefficient associated with each shift parameter n. Similarly, the the wavelet function,  may be expressed as:

(11)

Now any function, , can be written as a combination of the scaling and wavelet functions:

(12)

Scaling and wavelet functions obtained from the Haar function are illustrated in Figure 1.

Figure 1. Haar scaling and wavelet function, , and , respectively.

The wavelet transformation allows for operations at different scales:

(13)

where  is an orthogonal operator which maps the basis  onto .

The  projection of  and  by the operators  and  are defined as:

(14)

Using the Haar basis, the discrete form of operators  and  may be expressed as:

(15)

(16)

2.2. Wavelet-based Numerical Homogenization

The wavelet-based numerical homogenization method for linear problems was developed by Brewster and Beylkin [9], and begins with a linear matrix equation of the form typical of discretized boundary value problems, shown as:

(17)

where L is a bounded linear matrix operator, and U is the solution vector of unknowns. Specifically, acting within the subspace , we have:

(18)

Where the operator  acts on the space  at a resolution of r+1, and is composed of the set of basis functions spanning . Using the aforementioned scaling subspace decomposition:

(19)

And using the previously defined discrete projecting operators  and , the fine and coarse scale components of  can be extracted as follows:

(20)

(21)

(22)

(23)

Where the function  is split into a low scale component  as a projection onto , and a high-scale component  as a projection onto . Here  is the wavelet transformation operator, and the superscripts h and l denote the high and low-scale components, respectively. Performing the transformation from Equation 20, we have:

(24)

Where:

(25)

Here  and  denote the high and low-scale components of , respectively, and  is an orthogonal transformation, i.e., . The low-scale component  is obtained from the Schur complement [19] of  in Equation 24 to yield:

(26)

(27)

Where the Schur complement is defined as:

(28)

Here  is the coarse scale operator. The solution  of the reduced equation may be found simply from the projection of  onto . The Schur complement in Equation 26 acts on the coarser subspace . In the case when only the coarse-scale component is desired, it is sufficient to solve Equation 26.

To summarize, multiresolution wavelet-based numerical homogenization is performed by first solving for the solution at the finest scale. Thereafter, the low and high-scale components at the subsequent level of coarseness can be calculated from Equations 22 and 23. We may apply this projection recursively to produce the solution on  for any desired level of coarseness. The recursive process is shown in Figure 2.

Figure 2. Schematic illustrating the recursive homogenization procedure.

3. Results

In this section, we apply the wavelet-based numerical homogenization method to various closed form ordinary and partial differential equations, with the aim of achieving scale dependent solutions utilizing the aforementioned wavelet-based multi-resolution approach. In particular, we investigate exact and homogenized (scaled) solutions of equations with increasing levels of complexity, including; the one dimensional Elliptic equation, and the two-dimensional Laplace and Helmholtz equations. In each case, unless specified otherwise, the fine scale "exact" solutions are computed using the finite difference method.

As a first case, we consider the one-dimensional Elliptical equation, with appropriate boundary conditions:

(29)

With  (30)

Where A(x) various as: , ( as shown in Figure 3.

Figure 3. .

The discretized solutions pertaining to the finite difference solution included a spatial increment () equivalent to: , with  (corresponding to the total number of scale decompositions). The finite difference "exact" solution was computed using second-order central differences and Gaussian elimination, while the subsequent "coarse" scale solutions were computed in accordance with the method described previously.

Figure 4. Comparisons of exact versus homogenized solutions of the one-dimensional elliptical equation.

Figure 4 shows the results from the finite difference "Exact" solution as well as the homogenized solutions ranging from the finest scale ("L8") to the coarsest scale ("L2). As indicated, at successively larger scales, (i.e., "L4" and "L2") the amplitude of the periodic oscillations (resulting from the variable A(x)) becomes progressively diminished. Clearly the first scale decomposition ("L8") shows close agreement with the exact solution, and thus demonstrates the remarkable capacity of the method to approximate fine level details, if desired.

As a second case, we consider the two-dimensional Laplace equation:

(31)

With  (32)

The finite difference "exact" solutions were uniformly discretized such that:  (with ). Similar to the previous case, second-order central differences and Gaussian elimination were utilized. The results (scaled by  corresponding to the "exact" case and three subsequent (progressively coarsening) homogenization levels (L4, L3, and L2) are shown in Figure 5.

Figure 5. Comparisons of exact versus homogenized solutions (over four decomposition levels) for the two-dimensional Laplace equation.

For the L4 homogenized decomposition level, solutions from both the projection operator, , acting on the exact solution vector , as well as computations performed strictly from a knowledge of the linear matrix L and using the Schur complement [19] are shown in Figure 6. As indicated the two methods show equivalent results.

Figure 6. Comparisons of projected solution versus Schur complement (at decomposition level four) for the two-dimensional Laplace equation.

In the final case, we consider the two-dimensional Helmholtz equation:

(33)

With  (34)

Here, , and the simulation domain was discretized in the same manner as the previous case, namely;  (with ). The homogenization results are shown in Figure 7.

Figure 7. Comparisons of exact versus homogenized solutions (over four decomposition levels) for the two-dimensional Helmholtz equation.

Finally, and similar to the previous case, we found equivalent solutions between projected and Schur complement solutions, as indicated in Figure 8.

Figure 8. Comparisons of projected solution versus Schur complement (at decomposition level four) for the two-dimensional Helmholtz equation.

4. Conclusions

In this work we have investigated the use of wavelet-based numerical homogenization for the solution of various closed form ordinary and partial differential equations, with increasing levels of complexity. In particular, we have investigated exact and homogenized (scaled) solutions of the one dimensional Elliptic equation, the two-dimensional Laplace equation, and the two-dimensional Helmholtz equation. For the exact solutions, we utilized a standard Finite Difference approach with Gaussian elimination, while for the homogenized solutions, we applied the wavelet-based numerical homogenization method (incorporating the Haar wavelet basis), and the Schur complement) to arrive at progressive coarse scale solutions. The findings from this work provide for the following observations:

1)    The use of the wavelet-based numerical homogenization with various closed form, linear matrix equations of the type: , affords homogenized scale dependent solutions that can be used to complement multi-resolution analysis.

2)    The use of the Schur complement obviates the need to have an a priori exact solution, while the possession of the latter offers the use of simple projection operations.

Potential future efforts aligned with this study will focus on the utilization of this method for problems in higher dimensions (including temporal dependence), and investigate the use of various other wavelet basis functions.


References

  1. M. Ryvkin, "Employing the Discrete Fourier Transform in the Analysis of Multiscale Problems," Int. J. Multiscale Computational Engineering, 6, 2008.
  2. P. Wesseling,An Introduction to Multigrid Methods. Wiley, 1992.
  3. A. Brandt, "Multi-level adaptive solutions to boundary value problems," Math. Comp., 31, 1977.
  4. A. Toselli, and O. Widlund, "Domain Decomposition Methods—Algorithm s and Theory, Springer Series in Computational Mathematics, 34, Springer, New York, 2004.
  5. S. Thirunavukkarasu, M. Guddati, "A domain decomposition method for concurrent coupling of multiscale models," Int. J. Numerical Methods in Engineering, 92, 2012.
  6. L. Greengard, and V. Rokhlin, "A fast algorithm for particle simulations," J. Comput. Phys., 73, 1987.
  7. D. F. Martin, P. Colella, M. Anghel, and F.J. Alexander, "Adaptive Mesh Refinement for Multiscale Nonequilibrium Physics," Computing in Science and Engineering, 2005.
  8. I. Daubechies, Ten Lectures on Wavelets, SIAM, Philidelphia, 1992.
  9. M. Brewster, G. Beylkin, "A multiresolution strategy for numerical homogenization," Appl. Comput. Harmon. Anal., 2, 1995.
  10. A. Bensoussan, J. L. Lions and G.C. Papanicolaou, Asymptotic Analysis for Periodic Structures, North-Holland Pub. Co., Amsterdam, 1978.
  11. G.A. Pavliotis and A.M. Stuart, Multiscale Methods: Averaging and Homogenization, Springer-Verlag, New York, 2008.
  12. A. Chertock, and D. Levy, "On Wavelet-based Numerical Homogenization," Multiscale Model. Simul. 3, 2004.
  13. N.A. Coult, "A Multiresolution Strategy for Homogenization of Partial Differential Equations," PhD Dissertation, University of Colorado, 1997.
  14. E.B. Tadmor, M. Ortiz and R. Phillips, "Quasicontinuum analyis of defects in solids," Philos. Mag. A, 73, 1996.
  15. J. Knap and M. Ortiz, "An analysis of the quasicontinuum method," J. Mech. Phys. Solids, 49, 2001.
  16. Y. Meyer, "Ondelettes sur l’intervalle," Rev. Mat. Iberoamericana, 7(2), 1991.
  17. S. Mallat, Multiresolution Approximation and Wavelets, Technical Report, GRASP Lab, Dept. of Computer and Information Science, University of Pennsylvania.
  18. C. Basdevant, V. Perrier, and T. Philipovitch, "Local Spectral Analysis of Turbulent Flows Using Wavelet Transforms," Vortex Flows and Related Numerical Methods, J.T. Beale et al., (eds.), 1-26, Kluwer Academic Publishers, Netherlands, 1993.
  19. Z. Fuzhen, The Shur Complement and its Applications. Springer Pub., 2005.

Article Tools
  Abstract
  PDF(2471K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931