Revision as of 15:10, 4 November 2022

Abstract

This work aims to evaluate a parallelizable approximate solution model for the wave equation. For that, we used the temporal sweep known as the Waveform Relaxation method to guarantee the parallelization in space. However, this technique has limitations for this class of problems. Therefore, we proposed the combination of the Subdomain method in a non-conventional way in time with the Multigrid method, intending to reduce computational time and improve the convergence factors. In this work, we presented the mathematical analysis of the stability of the discretization model, which uses the Central Finite Difference method with weighting at each time step. As an application of the proposed method, in addition to a problem with a known analytical solution, we solved a wave propagation problem with reflection and phase inversion.

Keywords: Finite difference method, convergence factor, von Neumann criterion

1. Introduction

In this work, we intended to present an efficient and parallelizable method for solving sparse and large systems of equations that result from the discretization of the wave equation, which is a transient Partial Differential Equation (PDE) that models many problems found in several areas of applications. Among these problems are the vibration of strings and membranes, sound waves in gases or liquids, electromagnetic waves, transverse waves in solids, surface ocean waves, among others.

Explicit schemes for obtaining a solution of the wave equation are common in the literature, as in [1,2,3]. In general, such techniques are conditionally stable, which can be a disadvantage when performing refinements in time or space, as some criteria must be accepted for convergence. Another possibility is to use implicit methods, which are commonly unconditionally stable, thus assuring the reliability of the approximate solutions obtained [4].

The wave propagation problem can be studied in two manners, with the Helmholtz equation in the stationary form [5,6,7], or by directly solving the wave equation in the transient form [8,9,10,11]. In this context, we discretized the transient wave equation with the Finite Difference Method (FDM) weighted with a parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta }

at different time steps [12,13], thus generating an implicit method, which results in a linear system at each time step, which can be solved by using a solver such as Gauss-Seidel, with lexicographical or red-black order. 

One way to Speed-up the process of obtaining the system solution resulting from the discretization is to apply the Multigrid method, which significantly improves the convergence factors in the process of solving systems of equations [14,15]. According to Umetani et al. [5] and Franco et al. [16], the anisotropy related to physical and numerical factors generated with large values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha }

(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha }
being associated with wave propagation velocity) may be a challenge in solving the wave equation. 

According to Brandt and Livshits [7], there are limitations when attempting to solve the wave equation, even in its stationary form (Helmholtz Equation), because the solver loses efficiency when used in the standard Multigrid method. Therefore, the authors proposed modifications in the numerical experiments so that they would present better convergence rates.

Solutions with high-order compact methods for the wave equation were analyzed by Britt et al. [17], who studied the stability of explicit and implicit methods as well as the effectiveness of the Multigrid and Conjugate Gradients methods. The authors' analysis confirms the Multigrid effectiveness in solving problems with many degrees of freedom.

With the emergence of new technologies and high-performance computing, it became of paramount importance to develop algorithms that can use a large number of cores for data processing, as this greatly increases the efficiency in solving some problems involving PDEs [18].

In that context, a new method was developed: Waveform Relaxation (WR), which is an iterative method proposed to solve large systems of Ordinary Differential Equations (ODEs), but which can be adapted to time-dependent PDEs. In WR, the spatial domain is decomposed by a set of points and for each of these points, a system of ODEs is solved in all time steps [19,20,21,22]. A WR method was developed to solve the poroelasticity problem [23], which is modeled by a system of parabolic PDEs. Other works that apply parallelization are presented in Bellen and Zennaro [24] and Chartier and Philippe [25] for initial value problems and in Keller [26] for boundary value problems.

To non-steady state problems, the WR algorithms differ from the standard time sweep methods (Time-Stepping) in the fact that their iterates are functions in time [21,27]. The Partial Differential Equations is transformed into a large set of Ordinary Differential Equations, and an iterative algorithm can be used to solve this system. This numerical solution needs a high computational effort due to the necessity of solving systems of large dimension at each step point. WR iterations are designed in order to decouple the original large system in smaller subsystems: in this way, the iteration process can be implemented in a parallel computational environment, since each subsystem can be treated by a single processor [28].

In Ruprecht [29], the dispersion relation that occurred in the approximate solution was analyzed by using Parallel-in-Time, which is a time parallelization method used for solving hyperbolic equations. The author investigated propagation and stability characteristics and observed that instability in convergence is mainly caused by adopting medium and high wavenumbers.

Efficient solutions to the one-dimensional wave equation are already found in the literature, as in Baccouch and Temimi [30] for high-order methods and in Erbay et al. [31] for the non-linear cases. However, there are still challenges to be overcome when employing the Multigrid method, especially when combining with schemes that allow parallelization [11]. In this sense, the novelty of this work is the use of the Subdomains in Time method, combined with the Waveform Relaxation strategy and the Multigrid method, in order to reduce the large initial perturbations existing in Gander et al. [11]. Differently from Ong and Mandal [32], we work with a reduced number of subdomains in time, with the aim of reducing the CPU time and at the same time increase the degree of parallelization of the codes used.

The present work is organized as follows: In Section 2, we present the mathematical and numerical models adopted for the implicit discretization of the wave equation, as well as the stability of the numerical model and a foundation for the Multigrid method. In Section 3, we cover the details of the WR and Subdomain methods. In Section 4, we expose the results of simulations and comparisons between conventional WR and the method proposed in this paper. In Section 5, we present an application to the wave propagation problem with reflection, and finally, in Section 6, we present the conclusions.

2. Mathematical and numerical models

2.1 One-dimensional wave equation

Given a positive scalar Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha } , such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha ^2 =\dfrac{1}{V^2} } , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle V}

is related to the linear density and the stress in a string (wave propagation velocity), we present the one-dimensional wave equation [33], as

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle u(x,t)}

is the displacement at position Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x}
and time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t}

, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle f(x)}

is the initial configuration, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle g(x)}
is the initial velocity, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle l}
is the string length, and finally, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle u(0,t)}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle u(l,t)}
are the boundary conditions. This set of equations models a problem of vibration of a string fixed at the ends, in which the general solution is built with the fundamental frequencies of vibration, which are given by

where,

2.2 Discretization

Spatial and temporal discretizations are performed by using the Finite Difference Method (FDM), where the approximation process starts with the representation of the continuous domain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega }

by a discrete domain, which consists of an ordered set of points that form the grid [4]. In this way, it is possible to use a Taylor series expansion to represent an analytic function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Phi (x)}
in the neighborhood of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x_i}
and thus obtain an approximation for the second derivative of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Phi (x_i)}
given by

with a truncation error

Assuming the problem defined by Eqs. (1) to (4), we define the size of the spatial interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle h = \dfrac{l}{N_x-1}}

and the increment in time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \tau = \dfrac{t_f}{N_t-1}}

, with the number of spatial points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_x > 0}

and temporal points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_t > 0}

, for the final time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f > 0} . Assuming Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_i^k}

as an approximation for the solution Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle u}
at coordinate point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x_i}
and time step Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k}

, we can write Eq. (1) in the discretized form, applying weighting in the spaces [12], given by

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta }

is a weighting parameter. The  Figure 1 illustrates the points used to calculate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_i^k}

, with spatial coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle i} , at a certain time step Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k} .

Figure 1. Space-time discretization scheme for the 1D grid

By reordering the terms of Eq. (12), we obtain

with a truncation error of the order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle O(h^2\tau ^2,\tau ^4)} , given by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): - \dfrac{\alpha ^2 \tau ^2 h^2 \eta }{12} \dfrac{\partial ^{4} v_i^{k+1}}{\partial x^{4}} -...  - \dfrac{\alpha ^2 \tau ^2 h^2}{12}(1-2\eta )\dfrac{\partial ^{4} v_i^{k}}{\partial x^{4}} -... 

Assuming that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda =\dfrac{\alpha ^2 \tau ^2}{h^2}}

(herein called anisotropy factor), we have the following system of equations

where,

To perform the first iteration, it is necessary to know the solution in two previous time steps Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_{i}^{0}}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_{i}^{1}}

. To start the process, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_{i}^{0}}

is given by the initial setup while Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_{i}^{1}}
is given in Burden and Faires [4], by

2.3 Stability

Next, we will use the Von Neumann criterion [34] to determine the stability of the discretization method described in section 2.2. For that, let us assume that the global error is given by a Fourier series of local errors, also called harmonics. So, the error in the first time step can be expressed as:

with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \iota = \sqrt{-1}} . Note that we have a system with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_x+1}

equations and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_x+1}
unknowns, where the coefficient matrix is non-singular [12]. Now let us assume that a generic harmonic can be written in the form

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \beta \in \Re }

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma \in \mathbb{C}}

, both being arbitrary. Consequently, to analyze the stability of the discretization method, it is enough to verify the propagation of this harmonic as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k}

increases. By substituting Eq. (21) into Eq. (13), with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta=1/2}
[12,13], we have

or yet,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): -2e^{-\gamma}e^{\gamma k}e^{\iota \beta i} + e^{-\gamma}e^{\gamma k}e^{\iota \beta i}e^{-\iota\beta}]. 

By dividing both sides of Eq. (23) by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle e^{\gamma k}e^{\iota \beta i}}

and rearranging the terms, we have

Using Euler's formula, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle e^{\iota \beta } = \cos(\beta ) + \iota \sin(\beta )} , we can rewrite Eq. (24) as

or yet,

Using the trigonometric identities Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle (1-\cos(\beta ))=2 \sin^2 \left(\dfrac{\beta }{2}\right)}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \cosh(\gamma )=\dfrac{e^{\gamma }+ e^{-\gamma }}{2}}

, Eq. (26) can be rewritten as

or yet,

From Eq. (21) we have that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle U_i^{k+1}=e^{\gamma }U_i^k} , that is, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle e^{\gamma }}

is the amplification factor. Let us look at what happens to the generic harmonic Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle U_i^{k+1}}
as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k}
increases. From Eq. (28) we know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \beta \in \Re }

, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda \geq 0}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0~\leq ~\sin^2\left(\dfrac{\beta }{2}\right)~\leq 1}

, so it is enough to analyze the following cases:

1) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \sin^2\left(\dfrac{\beta }{2}\right) \rightarrow 1^-} , which implies that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma \rightarrow ~\arccos h\left(\dfrac{1}{1+2~\lambda }\right)} . In this case, the anisotropy factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

must be analyzed in the following situations:

1.1) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda \rightarrow +\infty } , which implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma \rightarrow \dfrac{\pi \iota }{2}} . Note that in this case the harmonic tends to stay the same as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle k}

increases, but it will not be amplified.

1.2) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda \rightarrow 0^+ } , which implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma \rightarrow 0^+} . Note that in this case Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle e^{\gamma }}

has a decreasing amplitude.

2) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \sin^2\left(\dfrac{\beta }{2}\right) \rightarrow 0^+} , regardless of the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } , we will have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \gamma \rightarrow 0^+} , which also produces a decreasing amplitude for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle e^{\gamma }} .

Given the above, the harmonics will not be amplified, since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0<e^{\gamma }<1} . Therefore, the discretization method used in Eq. (13) with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta = 1/2}

is unconditionally stable.

2.4 Multigrid method

In some cases, when discretizing PDEs that model physical problems, we can obtain sparse and large linear systems, as described by Eq. (15), which can be rewritten as

These systems can be solved by using direct or iterative methods (herein called solvers). Due to the characteristics of these systems, the direct methods become unfeasible due to the high computational cost [4]. In this case, we opt for iterative methods. However, these methods generally have good smoothing properties only at the beginning of the iterative process.

After a few iterations, the approximation error becomes smooth, but not necessarily small. This problem is due to the characteristic of classical iterative methods in quickly smoothing out high-frequency errors (oscillatory modes), leaving only low-frequency errors (smooth modes) [35].

In this context, the Multigrid method [36] can be applied. It is used for accelerating the convergence in obtaining the solution of this type of system, since when using a set of grids, it is possible to smooth both the oscillatory and smooth modes, as the smooth modes in fine grids become more oscillatory in coarser grids [14,37]. This approach allows the iterative process of the Multigrid method to act on all error components [38,39,40,41].

The way it runs through the different grid levels is called a cycle [42]. In this work, we used the V-cycle, shown below in Figure 2, where there is an example of a V-cycle for 5 levels of coarsening; from fine grid Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^h}

to the desired or coarsest grid Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^{16h}}

. Note that we use the coarsening ratio Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle q=2} , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle h}

being the spacing in the fine grid and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 2h}
the spacing in the immediately coarser grid.

Figure 2. Multigrid V-cycle

In this cycle, the system of equations is smoothed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nu _1}

times (pre-smoothing) in the fine grid, and then we restrict its residue to the immediately coarser grid with the restriction operators (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle I_h^{2h}}

). In this work, we used the full weighting operator, given by

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r_h}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r_{2h}}
are, respectively, the residue in the fine and coarse grid. This process is repeated until the coarsest grid is reached and only then the problem is solved

Next, the prolongation of corrections is performed by using the linear interpolation operator (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle I_{2h}^h} ), given by

where the first equation is for even Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle i}

and the other is for odd Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle i}

, in the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^h} . The solution is then corrected and the system of equations is smoothed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nu _2}

times (post-smoothing), and the process is repeated until the finer grid Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^h}
is reached, where the solution is smoothed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \nu _2}
times [39]. The V-cycle is repeated until the stopping criterion is met. This approach allows the iterative process of the Multigrid method to smooth all the components [43].

3. Waveform relaxation and the subdomain methods

Waveform Relaxation (WR) is an iterative method that was initially proposed to solve large systems of Ordinary Differential Equations (ODEs) [19], but it can also be applied in time-dependent PDEs, where the spatial domain is decomposed by a set of points, and for each of them a system of ODEs is solved in all time steps [22,23,44,45]. This method allows the parallelization of algorithms for transient PDEs to be performed. According to [46], the feature of the WR method that transforms PDEs into an ODE system presents the form

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle G_i}

are vectors or functions that contain temporal information for each spatial coordinate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle i}

, and which is calculated with the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_i=(v_1,v_2,v_3,...v_d)} . Thus, for each node Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x_i}

of the spatial discretization, a temporal ODE is solved to the final time independently. Each component of the system given in Eq. (32) can be written as an ODE, as follows

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle d}

is the dimension of the system and the notations Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle v_i(0) = v^0_i}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \dfrac{d v_i}{dt} = g_i^0}
 with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle  1 \leq i \leq d,}
indicate respectively, the initial configurations and velocities, for each point of the spatial discretization. Each line of the system of Eqs. (33) can be solved separately using a core for each line, as illustrated in  Figure 3 for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_x = 12}

.

Figure 3. Waveform Relaxation method

Each temporal ODE can be solved in all spatial nodes separately, where the update of unknowns can be performed at the end of a WR cycle. Thus, we have an iterative method of repeating the procedure until a stopping criterion is reached [47]. We can obtain a fully parallelizable method in space by using a colored ordering scheme in the solver, such as Gauss-Seidel Red-Black (GSRB) [45].

It is possible to combine Waveform Relaxation and the Multigrid method when performing coarsening only in the spatial direction because WR is continuous in time. This way, the number of temporal discretization points is kept constant [45]. For example, for a fine grid Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^h}

with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle  N_x \times N_t =33 \times 33}
points, the coarser grids, with a coarsening ratio Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle q=2}

, are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^{2h}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^{4h}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^{8h}}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega ^{16h}}

, which respectively have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 17 \times 33} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 9 \times 33} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 5 \times 33}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 3 \times 33}
points. Then, a Multigrid cycle is performed at all spatial points for all time steps. In Algorithm 1, the structure of the Waveform Relaxation and Multigrid is presented for the solution of system Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle A_h(t)v_h(t) = f_h(t)}

, adapted from [23].}

Solve with a direct or fast solver.

Pre-smoothing: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \nu_1
 steps of the GSRB Waveform Relaxation.

 Compute the defect.

Restrict the defect.

Solve the defect equation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): G_{2h}
by performingone V-cycle of WRMG.     

Interpolate the correction.

 Compute a new approximation.

Post-smoothing: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \nu _2
steps of the GSRB Waveform Relaxation.

In Gander et al. [11] there is a variation of the Waveform Relaxation method, which can be applied to PDEs, where the domain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega }

is divided into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K}
spatial subdomains. Remember that each point is solved independently and continuously until the final time, which generates a parallelizable strategy. See  Figure 4 for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=3}

.

Figure 4. Division of the domain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \Omega into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K=3 spatial subdomains

We can notice that in the case where the subdomains are the smallest possible, the subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega _1, \Omega _2, ... , \Omega _K}

are respectively equal to the points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x_1, x_2, ... , x_{N_x}}

. That is, we will have the standard Waveform Relaxation method. Note that parallelization can be performed by using a processing core for each spatial subdomain.

In Gander et al. [11] and Gong et al. [48] a study is carried out to assess the stability of using this approach for heat and Helmholtz equations, as well as the ways of exchanging information between the subdomains. The authors also mention that at the beginning of the iterative process, the convergence is negatively affected, and perturbations may occur in the approximate solution, but as the iterative process advances, the solution converges to the desired values. See Figure 5, taken from Gander et al. [11].

Figure 5. Error for the heat equation with Waveform Relaxation by spatial subdomains [11]

In this case, Gander et al. [11] shows the convergence for the one-dimensional heat transfer problem with the method called Dirichlet-Neumann Waveform Relaxation. In the left figure, the author presents the theoretical error (error) and the numerical error (bound) obtained with five fixed spatial subdomains and different final times (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle T} , as used in the figure). In the right figure, the number of subdomains varies, and the final time is fixed at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle T = 2} s. We can notice that the initial oscillations are higher when the final time is higher and/or there are more subdomains in space. Here we have a great challenge: the higher the number of subdomains, the higher the degree of parallelization; however, the oscillations at the beginning of the iterative process will be also higher.

Another approach is proposed in Ong and Mandal [32], where, besides the division in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K}

spatial subdomains, there is also a division in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}
temporal subdomains, thus generating an approach that is highly parallelizable (see Figure 6 for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K = 3}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J = 2}

).

Figure 6. Waveform Relaxation method by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K = 3 spatial and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J = 2 temporal subdomains

Notice that the approach proposed in Gander et al. [11] is a specific case of the approach presented in Ong and Mandal [32], which adopts Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J = 1} . In this work, we propose a thorough analysis of the second methodology, which adopts the minimum number of spatial subdomains (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1} ) and a reduced number of temporal subdomains, to solve the wave equation with the WR method, aiming to reduce the oscillations at the beginning of the iterative process. For this, we analyze the effect of parameters such as time and space interval, physical properties of the wave, number of temporal subdomains, among others. This method is applied using recursively the Algorithm 1 according to Figure 7.

Efficient solutions to the one-dimensional wave equation are already found in the literature, such as in Baccouch and Temimi [30] for high-order methods and in [31] for nonlinear cases. However, there are still challenges to solve when using the Multigrid method, especially when combined with schemes that allow parallelization, as in Gander et al. [11]. In this sense, one of the novelties of this work focuses on the use of the Subdomains in Time method, combined with the Waveform Relaxation strategy and the Multigrid method, in order to reduce the existing large initial oscillations. Unlike the Ong and Mandal [32], here we work with a reduced number of subdomains in time, in order to reduce CPU time while increasing the degree of parallelization of the codes used.

Figure 7. Waveform relaxation with subdomain method

4 Results

In this section, we present the main results of this work, where we solve a one-dimensional problem with Dirichlet boundary conditions, Eqs. (1) to (4), which serves to validate the proposed methodology. We approach techniques of code verification based on the errors of the numerical simulations and on a posteriori analyses of the results found with the Multigrid (with V-cicle(2,2)) and Singlegrid formulations. In our analyses, we use the Gauss-Seidel solver with Red-Black ordering. Then, we discuss the characteristics of the application of the standard Waveform Relaxation method in the one-dimensional wave equation and some problems regarding the use of this formulation. To deal with these problems, we apply the Subdomain Method proposed by Ong and Mandal [32]. We innovate by assuming a fixed parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1}

with variation only in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}

. Finally, we analyze the convergence factors, complexity order (with a non-linear adjustment), CPU time, and Speed-ups.

The one-dimensional wave propagation problem modeled by Eqs. (1) to (4) is solved by admitting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha = 2} , with initial condition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle f(x)=\sin(\pi x)}

and initial velocity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle g(x)=0}

. We adopt the same number of points in the spatial and time discretization Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N_x = N_t }

(denoted by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N}

), weighting parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta = 0.5} , final time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f = 1.0s}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x \in (0,1)}

. Tests were performed in a computer with Intel Corei3 1.5 GHz processor, 4 GB RAM, and 64-bits Windows 10 operational system with double precision.

4.1 Discretization error

The discretization error is related to the truncation in the Taylor series [4] and consequently, to the size of the grid elements. For the sake of assessing the behavior of this type of error, we disregard iteration and round-off errors. For this, each problem was solved until the round-off error was reached. Next, we present in Figure 8 the infinity norm of the error in the solution approximated with the Waveform Relaxation (WR), combined with the Multigrid (MG) and Singlegrid (SG) for values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N} .

Figure 8. Infinity norm of the discretization error for different grid sizes with the Waveform Relaxation method

We noticed that the discretization error decreases as the grid is refined. The errors presented in Figure 8 are the same found in Malacarne et al. [13] using the Time-Stepping method, which generates a 4th-order method, which can be easily verified using the methodology present in da Silva et al. [49]. This test serves to verify the code used here, which utilizes time sweeping given by WR.

4.2 Oscillations in the approximate solution

Next, we show the oscillatory behavior of the solution during the iteration process, when using the Waveform Relaxation method. For such, we solve a one-dimensional problem modeled by Eqs. (1) to (4), using Singlegrid (SG) and Gauss-Seidel with Red-Black ordering as the solver, in a grid with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N = 129}

points. Figure 9 presents the solutions for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 2}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 50}
iterations, and  Figure 10 shows the solutions for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 200}
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 1000}
iteration, both using final time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f = 1.0s}

.

Figure 9. Solution with 2 (left) and 50 iterations (right)

Figure 10. Solution with 200 (left) and 1000 iterations (right)

We verified significant initial oscillations when applying the standard WR method, even when using coarser grids (with fewer points). Despite the strong oscillation at the beginning of the process, the numerical solution converges to the desired values as a large number of iterations are performed.

In Figure 11 it is possible to observe the behavior of the infinity norm of the residue as the iterations are performed, for Singlegrid and Multigrid.

Figure 11. Residue versus iterations for singlegrid and multigrid

Even though MG performs fewer cycles than SG, the order of perturbation of the residue of both is the same. This initial perturbation is not a desirable characteristic in the approximation process and despite being well-known in the literature, its causes remain an unknown [11] and negatively interfere in the convergence factors and in the CPU time.

In Figure 12, we present the infinity norms of the residues for different numbers of points, with final time fixed at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f=1.0s}

(left), and then varying the final time Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f}

, with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N =2^7 +1}

(right), using SG and standard WR.

Figure 12. Residue versus iterations varying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): t_f = 1.0s (left), and varying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): t_f , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N=2^7+1 (right)

Notice that with the increase in the final time, the maximum residue increases considerably, at the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{25}} , similarly to what happens when the number of points in the grid increases. This implies a loss of efficiency when solving problems with WR and Singlegrid with many degrees of freedom and/or a final time relatively large. Very similar residues are found when applying the Multigrid method for these cases, as seen in Figure 11.

4.3 Average convergence factor - Standard waveform relaxation

Here we apply the standard Waveform Relaxation method for the problem described in the previous section, but with varying final time. For this, let the convergence factor be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho =||r^{it}||_\infty /||r^{it-1}||_\infty } , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle r^{it}}

being the residue generated in the iteration Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle it}

. We know that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho \approx 0}

results in more efficient methods, while Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho \approx 1}
means the opposite [50]. We also define the average convergence factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}
[39], by

According to Thole and Trottenberg [51] and Horton and Vandewalle [52] Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda = \alpha ^2\tau ^2/h^2}

can be considered as a measure of the anisotropy level in the discretized operator in a given grid, and such anisotropy can affect the performance of the solver. As Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }
depends on the temporal and spatial increments adopted in the discretization and on the velocity of the propagation of the wave, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }
thus represents a measure of physical and geometrical anisotropy of the wave equation.

We can write the final time depending directly on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha }

, with the expression Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f=\sqrt{\lambda }/\alpha } . Then, we present the test results, where we vary the value of the parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

and calculate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}
for a wide range of problems, which covers the vast majority of real cases of wave propagation. In order to verify the behavior of the standard Waveform Relaxation method, using the Singlegrid and Multigrid Methods (Figure 13).

Figure 13. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \rho _m versus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \lambda with standard Waveform Relaxation using Multigrid and Singlegrid

We can observe in Figure 13, that as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

increases, the average convergence factors of the Multigrid and Singlegrid Methods also increase, becoming Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 1.0}

, which is not good. With this, we can conclude that the solution model is neither efficient nor robust for intermediate or large Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

values (in this cases we have many unkwows and longer final times). This result supports the hypothesis that it is inefficient to apply the standard Waveform Relaxation method to solve the wave equation, whether with the Multigrid or Singlegrid methods.

The hyperbolic transient wave computational simulation problem can be solved in different ways, but most of them have limitations, especially for relatively large end times. For these cases, explicit schemes exhibit instabilities that compromise the reliability of the approximate solution [53]. As we have seen, even implicit methods present difficulties to solve these cases, because at the beginning of the iterative process, the approximate solutions present strong oscillations, which are smoothed out as the number of iterations increases (Figures 9 and 10), but this seriously compromises the efficiency of such methods. Therefore, we seek to improve the applicability of parallelizable methods, such as the Waveform Relaxation Method. For this, we combine the methodology developed so far with the Subdomains in Time method.

4.4 Applying the subdomain method

From this section on, we present the results of the Waveform Relaxation Method combined with the Subdomain in Time method. For this, we will always adopt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1}

for the number of spatial subdomains. For the number Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}
of subdomains in time, we will always adopt the smallest possible value, but one that is able to provide good average convergence factors (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}

). Next in Table 1 are the values used for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} , which may vary depending on the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N^2=N_xN_t}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

. The choice of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}

was based on empirical analysis of this data so that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0.4}

, ie, so that the implicit numerical model can be considered acceptable [39].

of subdomain in time according to the ranging of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N
and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \lambda 

- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \lambda 

We should also note that, for large Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} , the number of spatial meshes within each temporal subdomain will be small, which may reduce the level of parallelization of the method. Thus, it is always interesting to have the smallest possible value for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} , but in the case of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=1} , we have the standard Waveform Relaxation method, which we already know is not efficient. We point out that all the following tests were performed using the number of subdomains in time that are present in the Table 1.

It is also possible to notice that for domains with small Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N} , the largest number of subdomains in time is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=2} , regardless of the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } . But for problems with large Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N} , depending on the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } , we cannot work with a very small number for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} , because the instabilities of the standard Waveform Relaxation will negatively affect the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m} .

To solve the problem of higher residues during the initial iterations, we analyzed the method parameters as proposed by Ong and Mandal [32], with the goal to improve the average convergence factors. We kept the number of spatial subdomains fixed at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1}

and analyzed the number of temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}

. This way, we obtained a highly parallelizable strategy when using the Waveform Relaxation method. Figure 14 shows the behavior of the residue, using SG and WR for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N = 2^8 +1}

that is, a total of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 66049}
points, with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f=1.0s}

.

Figure 14. Residues versus iterations for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): t_f = 1.0s , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N=2^8+1 and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K=1 , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J=1 (left) and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J=4 (right)

By solving the wave equation with SG and WR using only one temporal subdomain (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=1} ), we have the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU}~=~14.15 s} , with a maximum residue of the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{53}} . However, by using four temporal subdomains (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=4} ), where the subdomain values vary from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.0s}

to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.25s}

, from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.25s}

to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.50s}

, from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.50s}

to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.75s}

, and from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 0.75s}

to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 1.0s}

, we have the maximum residue of the order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{12}}

and the processing time is reduced to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU}=4.01s}

.

In Figure 15 we can observe the behavior of the order of the maximum residue concerning the number of temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} , as well as the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N} , considering Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1} .

Figure 15. Residue versus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J , for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): t_f = 1.0s and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K=1 , varying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N , with SG and WR

We verified that the largest reductions in the residue are found in the first subdivisions of the domain. For instance, for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N=2^8 +1}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=1}

, the maximum residue has an order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^{53}}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU}=14.15s}

, however, when using Subdomain Method, this residue decreases to an order of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 10^5}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU}=2.35s}

. We further highlight the considerable improvement in the order of residue and computational time.

4.5 Average convergence factor - Waveform relaxation with subdomain in time

Next, Figure 16 presents the average convergence factors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}

for the Multigrid and Singlegrid methods with different values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }
for different values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N}

, combined with the Waveform Relaxation method, where the choice of the appropriate number of subdomains was made based on Table 1.

Figure 16. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \rho _m for the Multigrid and Singlegrid methods, combined with Waveform Relaxation Relaxation, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K=1 and suitable Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J

In this case, we used the same number of subdomains for the MG and SG. We found out that both methods present Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0} , for values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle log_2(\lambda ) < 0} , which implies high efficiency. But, as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle log_2(\lambda )}

 increases, the SG shows values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 1}
with the refinement of the grid, that is, the method is inefficient in this region. In the same region, the MG shows values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0.45}
with the refinement of the grid. In the worst case, in the region near Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda=10^2}

, the MG presents Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0.6} , though it still shows lower convergence factors than those presented by the SG method.

Therefore, the MG method proposed for the wave equation is much more efficient for these values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } . Besides, we notice that the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}

tend to not depend on the value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }
for finer grids, which evidences the robustness of the method. In this work, high values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }
can mean higher final times or wavenumbers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha }

, or even, highly refined spatial grids.

An example can be given for the case Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda = 10^4}

, with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N = 2^8 +1}

, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 16}

temporal subdomains and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 1}
spatial subdomain. For the SG method, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU} = 1320.62s}

, with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0.9999}

and a total of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 120 000}
iterations. For the MG method, we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{CPU} = 4.67s}

, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m \approx 0.4301} , and a total of 23 V-cyclesFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle (2,2)} , which confirms the advantage of employing the MG combined with the Subdomain technique for the WR proposed in this work, that is, temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}

and spatial subdomain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1}

. A possible explanation for this advantage can be found in the reduction of the average convergence factor of the MG method with the increase in the number of temporal subdomains (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J} ), as seen in Figure 17.

Figure 17. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \rho _m for the MG and SG methods with Waveform Relaxation and different numbers of temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \lambda = 10^5

4.6 Order of complexity

We made a geometrical adjustment [4] to verify the complexity of the algorithm that uses WR combined with subdomains and compared the results for Single and Multigrid. For this, we used the following expression

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle c}

is the coefficient of the method, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle p}
represents the order of complexity of the solver related to the slope of the adjustment curve and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbf{N}}
is the total number of variables of the problem, which in our case will be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle ~\mathbf{N}~=~(N_x~-~2)~.~(N_t~-2~)~}

. Theoretically, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle p}

must be near Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 1}
for the Multigrid method [14]. Table 2 shows the results for these parameters, with different values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

. To find the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } , we kept Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \mathbf{N}}

fixed and varied the final time.

As the values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

increase, the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle p_{MG}}
tends to values near Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 1}
and the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle p_{SG}}
near Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 2}

. This trend confirms the linear behavior of the Multigrid method and highlights the disadvantage of using the Singlegrid method for large values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } , which corroborates the results depicted in Figures 16 and 17.

4.7 Speed-up

In this section, we analyze the Speed-up, which is given by the ratio between the computational time of the SG and the MG. Figure 18 shows the Speed-up results for increasing number of points of the problem (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N^2} ), for different values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } , considering Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle K=1}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=8}

.

Figure 18. Speed-up versus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): N^2 for different values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): \lambda , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): K=1 and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): J=8

Notice that the Speed-up increases along with the increase in the number of points (desirable property) and also for higher values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda } . For example, when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda = 10^5} , with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N=2^8~+1}

and temporal subdomain Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=8}

, the MG method has a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{cpu} = 8.13s}

and the SG a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_{cpu} = 1477.82s}

. That is, the MG method solves the problem roughly Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 182}

times faster than the SG method.

5. Application: Wave propagation problem with reflection

Here we approach a more realistic problem that is solved by approximation. We admit Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \Omega = [0,1]} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \alpha = 2} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f = 1.0s} , initial configuration and velocity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle f(x)=g(x)=0} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle u(0,0)=u(1,t)=0} , that is, we have a straight string in rest position in the initial time, fixed at both ends. Time can be divided in the intervals Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_1,t_2,t_3,...,t_{p-1},t_p,t_{p+1},...,2t_p,...,t_f} , where the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_p}

is the time in which the oscillation reaches the maximum displacement. Then, we apply a pulse in the extremity Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle x=0}

, between the interval Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle (t_3; 2t_p)} . This pulse can be inserted into the problem, given by the following boundary conditions

In this work, we adopt Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_p = 0.109s} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle 2t_p = 0.218s} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle t_f = 1.000s} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda = 10^0}

and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle N = 2^6 +1}

. One can verify the propagation of the pulse as time varies on Figure 19.

Figure 19. Propagation of pulse on a string as time advances

By observing Figure 19, from left to right and from top to bottom, we can verify the phenomenon of wave propagation on a string, where there is an inversion of the phase in which the pulse was applied. We solve this problem by applying the WR method with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=1}

(standard) and WR with temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=4}
, combined with the SG and MG for both cases.  Table 3 shows some of the parameters assessed.

By using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J=4} , the analyzed parameters improve significantly, especially the average convergence factor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \rho _m}

combined with MG, thus proving the efficiency of this applied method for the wave equation.

6. Comments

The methodology presented here, can be extended also to more realistic problems, by considering the external forces operating on the problem, by inserting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle F(x, t)}

in the right hand side of Eq. (1), because according to Trottenberg et al. [14] causes changes only source term of the system of equations, not changing the performance of the method. Another possibility is to check the applicability of the Waveform Relaxation method with Subdomains in Time to two-dimensional and three-dimensional problems. As well as the application of the Multigrid method, which as seen in this article, can signifcantly decrease the average convergence factors, making it possible to obtain powerful parallelizable methods.

7. Conclusions

In this work, we presented a scheme of parallelizable solutions for the one-dimensional wave propagation problem that uses discretization combined with the Finite Difference Method, weighted by a parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \eta }

in different stages of time. The innovation can be seen in the application of the Waveform Relaxation method with temporal subdomains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle J}
and only one spatial subdomain, in which we were able to significantly reduce the order of the maximum residue. We also innovated when applying the Multigrid method for this class of problems and we showed a considerable improvement in the processing time and convergence factors, in codes that allow parallelization, mainly when working with large values of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://mathoid.scipedia.com/localhost/v1/":): {\textstyle \lambda }

. Moreover, we applied this technique to analyze the solution of a problem of pulse propagation on a string, thus proving the efficiency of the proposed method.

We also point out that the main challenge of using the Waveform Relaxation method for the wave equation is in the initial increase of the residual, since this negatively alters all the parameters analyzed, and that it was already known in the literature [11]. We emphasize that this problem was solved satisfactorily with the methodology presented in this work.

Disclosure statement: No potential conflict of interest was reported by the authors.

Funding: This study was financed in part by the Coordenco de Aperfeicoamento de Pessoal de Nível Superior (CAPES), Finance Code 88882.381810/2019-01.

References

[1] Weber I., Kreiss G., Nazarov M. Stability analysis of high order methods for the wave equation, Journal of Computational and Applied Mathematics, 404:113900, 2022.

[2] Gander M.J., Halpern L., Nataf F. Optimal Schwarz waveform relaxation for the one dimensional wave equation. SIAM Journal on Numerical Analysis, 41(5):1643&-1681, 2003.

[3] Bamberger A., Glowinski R., Tran Q.H. A domain decomposition method for the acoustic wave equation with discontinuous coefficients and grid change. SIAM Journal on Numerical Analysis, 34(2):603-639, 1997.

[4] Burden R., Faires J.D. Numerical analysis. Brooks/Cole Cengage Learning, pp. 882, 2016.

[5] Umetani N., MacLachlan S.P., Oosterlee C.W. A multigrid-based shifted Laplacian preconditioner for a fourth-order Helmholtz discretization. Numerical Linear Algebra with Applications, 16(8):603–626, 2009.

[6] Ernst O.G., Gander M.J. Multigrid methods for Helmholtz problems: a convergent scheme in 1D using standard components. Direct and Inverse Problems in Wave Propagation and Applications, De Gruyer (Ed.), 135-186, 2013.

[7] Brandt A., Livshits I. Wave-ray multigrid method for standing wave equations. Electronic Transactions on Numerical Analysis, 6:162-181, Kent State Univesity, 1997.

[8] Dehghan M., Mohebbi A. The combination of collocation, finite difference, and multigrid methods for solution of the two-dimensional wave equation. Numerical Methods for Partial Differential Equations: An International Journal, 24(3):897–910, 2008.

[9] Malacarne M.F., Pinto M.A.V., Franco S.R. Computational simulation of one-dimensional waves with the Multigrid Method. Brazilian Journal of Development, 7(8):83763–83775, 2021.

[10] Gander M.J., Halpern L., Rannou J., Ryan J. A direct time parallel solver by diagonalization for the wave equation. SIAM Journal on Scientific Computing, 41(1):A220–A245, 2019.

[11] Gander M.J., Kwok F., Mandal B.C. Dirichlet–Neumann waveform relaxation methods for parabolic and hyperbolic problems in multiple subdomains. BIT Numerical Mathematics, 173–207, Springer, 2021.

[12] Cuminato J.A., Meneguette M. Discretization of partial differential equations: finite difference techniques (in Portuguese). Brazilian Mathematical Society, 2013.

[13] Malacarne M.F., Pinto M.A.V., Franco S.R. Performance of the multigrid method with time-stepping to solve 1D and 2D wave equations. International Journal for Computational Methods in Engineering Science and Mechanics, 23(1):45–56, Taylor & Francis, 2022.

[14] Trottenberg U., Oosterlee C.W., Schuller A. Multigrid. Elsevier, pp. 631, 2000.

[15] Wienands R., Oosterlee C.W. On three-grid Fourier analysis for multigrid. 23. SIAM. SIAM Journal on Scientific Computing 2 651–671, 2001.

[16] Franco, Sebastião Romero and Gaspar, Francisco Jose and Pinto, Marcio Augusto Villela and Rodrigo, Carmen. (2018) Multigrid method based on a space-time approach with standard coarsening for parabolic problems, 317. Elsevier. Applied Mathematics and Computation 25–34.

[17] Britt, Steven and Turkel, Eli and Tsynkov, Semyon. (2018) A high order compact time/space finite difference scheme for the wave equation with variable speed of sound, 76. Springer. Journal of Scientific Computing 2 777–811.

[18] Gander, Martin J and Neumuller, Martin. (2016) Analysis of a new space-time parallel multigrid algorithm for parabolic problems, 38. SIAM. SIAM Journal on Scientific Computing 4 A2173–A2208.

[19] Lelarasmee, E. and Ruehli, A. E. and Vincentelli, S. A. L. (1982) The Waveform Relaxation Method for Time Domain Analysis of Large Scale Integrated Circuits Theory and Apllications. IEEE Trans. Comput. Aided Design Integr. Circ. Systems 1 131-145.

[20] Lubich, Ch and Ostermann, A. (1987) Multi-grid dynamic iteration for parabolic equations, 27. Springer. BIT Numerical Mathematics 2 216–234.

[21] Vandewalle, S. and Horton, G. (1993) Multicomputer-Multigrid Solution of Parabolic Partial Differential Equations. Multigrid Methods IV: Proceedings of the Fourth European Multigrid Conference. Springer Basel AG 97-109.

[22] Gander, Martin Jakob. (1996) Overlapping Schwarz for linear and nonlinear parabolic problems. 9th International Conference on Domain Decomposition Methods 97–104.

[23] Franco, Sebastião Romero and Rodrigo, Carmen and Gaspar, Francisco Jose and Pinto, Marcio Augusto Villela (2018) A multigrid waveform relaxation method for solving the poroelasticity equations, 37. Springer. Computational and Applied Mathematics 4 4805–4820.

[24] Bellen, Alfredo and Zennaro, Marino. (1989) Parallel algorithms for initial-value problems for difference and differential equations, 25. Elsevier. Journal of Computational and applied mathematics 3 341–350.

[25] Chartier, Philippe and Philippe, Bernard. (1993) A parallel shooting technique for solving dissipative ODE's, 51. Springer. Computing 3-4 209–236.

[26] Keller, Herbert B. (1992) Numerical methods for two-point boundary-value problems. Courier Dover Publications.

[27] Gander, Martin J. (2015) 50 Years of Time Parallel Time Integration. Springer International Publishing 69-113.

[28] Conte, Dajana and D'Ambrosio, Raffaele and Paternoster, Beatrice. (2016) GPU-acceleration of waveform relaxation methods for large differential systems, 71. Springer. Numerical Algorithms 2 293–310.

[29] Ruprecht, Daniel. (2018) Wave propagation characteristics of Parareal, 19. Springer. Computing and Visualization in Science 1-2 1–17.

[30] Mahboub Baccouch and Helmi Temimi. (2021) A high-order space–time ultra-weak discontinuous Galerkin method for the second-order wave equation in one space dimension, 389. Journal of Computational and Applied Mathematics 113331.

[31] H. A. Erbay and S. Erbay and A. Erkip. (2021) A semi-discrete numerical method for convolution-type unidirectional wave equations, 387. Journal of Computational and Applied Mathematics 112496.

[32] Ong, Benjamin W and Mandal, Bankim C. (2018) Pipeline implementations of Neumann–Neumann and Dirichlet–Neumann waveform relaxation methods, 78. Springer. Numerical Algorithms 1 1–20.

[33] Olver, Peter J. (2014) Introduction to partial differential equations. Springer.

[34] Thomas, James William. (2013) Numerical partial differential equations: finite difference methods, 22. Springer Science & Business Media.

[35] Wesseling, Pieter. (1995) Introduction to multigrid methods.

[36] Brandt, Achi and Livshits, Irene. (1977) Multi-level adaptive solutions to boundary-value problems, 31. Mathematics of Computation 138 333-390.

[37] Brandt, Achi and Livne, Oren E. (2011) Multigrid techniques: 1984 guide with applications to fluid dynamics, 67. SIAM.

[38] Elman, Howard C and Ernst, Oliver G and O'leary, Dianne P. (2001) A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations, 23. SIAM. SIAM Journal on scientific computing 4 1291–1315.

[39] Trottenberg, Uaa and Clees, Taa. (2009) Multigrid software for industrial applications-from MG00 to SAMG. 100 s of ‘Notes on Numerical Fluid Mechanics’. Springer 423–436.

[40] Rutz, Grazielli Vassoler and Pinto, Marcio Augusto Villela and Goncalves, Simone de Fátima Tomazzoni. (2019) On the robustness of the multigrid method combining ILU and Partial Weight applied in an orthotropic diffusion problem, 35. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería.

[41] Anunciação, Márcio Alexandro Maciel and Pinto, Marcio Augusto Villela and Neundorf, Réverton Luis Antunes. (2020) Solution of the navier-stokes equations using projection method and preconditioned conjugated gradient with multigrid and ilu solver, 36. Revista Internacional de Métodos Numéricos para Cálculo y Diseño en Ingeniería.

[42] Laís de Oliveira, Michely and Pinto, Marcio Augusto Villela and Goncalves, Simone de Fátima Tomazzoni and Rutz, Grazielli Vassoler. (2018) On the robustness of the xy-zebra-gauss-seidel smoother on an anisotropic diffusion problem, 117. Tech Science Press. Computer Modeling in Engineering & Sciences 2 251–270.

[43] Falgout, Robert D and Friedhoff, Stephanie and Kolev, Tz V and MacLachlan, Scott P and Schroder, Jacob B and Vandewalle, Stefan. (2017) Multigrid methods with space–time concurrency, 18. Springer. Computing and Visualization in Science 4-5 123–143.

[44] Jun Liu and Yao-Lin Jiang. (2011) Waveform relaxation for reaction–diffusion equations, 235. Journal of Computational and Applied Mathematics 17 5040-5055.

[45] Vandewalle, Stefan. (2013) Parallel multigrid waveform relaxation for parabolic problems. Springer-Verlag.

[46] Vandewalle, S. and Horton, G. (1995) Fourier Mode Analysis of the Multigrid Waveform Relaxation and Time-Parallel Multigrid Methods, 54. Computing 317-330.

[47] Crow, ML and Ilic, M. (1990) The parallel implementation of the waveform relaxation method for transient stability simulations, 5. IEEE. IEEE Transactions on Power Systems 3 922–932.

[48] Gong, Shihua and Gander, Martin J and Graham, Ivan G and Lafontaine, David and Spence, Euan A. (2021) Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation. Cornell University. Numerical Analysis.

[49] da Silva, Luciano Pereira and Rutyna, Bruno Benato and Righi, Aline Roberta Santos and Pinto, Marcio Augusto Villela. (2021) High Order of Accuracy for Poisson Equation Obtained by Grouping of Repeated Richardson Extrapolation with Fourth Order Schemes, 128. Tech Science Press. Computer Modeling in Eengineering & Sciences 2 699–715.

[50] Briggs, W. L. and Henson, V. E. and McCormick, S. F. (2000) A Multigrid Tutorial. SIAM, 2nd Edition.

[51] Thole, Clemens-August and Trottenberg, Ulrich. (1986) Basic smoothing procedures for the multigrid treatment of elliptic 3D operators, 19. Elsevier. Applied Mathematics and Computation 1-4 333–345.

[52] Horton, Graham and Vandewalle, Stefan. (1995) A space-time multigrid method for parabolic partial differential equations, 16. SIAM. SIAM Journal on Scientific Computing 4 848–864.

[53] Bailly, Christophe and Juve, Daniel. (2000) Numerical solution of acoustic propagation problems using linearized Euler equations, 38. AIAA journal 1 22–29.