An Analysis of some Properties of Class of Elliptic Partial Differential Operators: a Solution of some Problems

This paper describes a method for rapidly solving large systems of linear equations with sparse coefficient matrices. It is capable of handling the equations arising from the finite element or finite difference discretization of elliptic partial differential equations such as Laplace's equation, as well as the systems associated with heat conduction and random walks on certain networks. While most existing fast schemes for such problems rely on iterative solvers, the method described here solves the linear system directly (to within a preset computational accuracy). This obviates the need for customized pre-conditioners, improves robustness in the handling of ill-conditioned matrices, and leads to dramatic speed-ups in environments in which several linear systems with the same coefficient matrix are to be solved. The scheme is described for the case of equations defined on a uniform square grid. Extensions to more general grids, including those associated with complicated geometries and local mesh refinements are possible. For a system matrix of size NxN (corresponding to agrid), the scheme requiresarithmetic operations. For a single solve, only storage is required. Moreover, for problems loaded on the boundary only, any solves beyond the first require onlyarithmetic operations provided that only the solution on the boundary is sought. For problems loaded on the entire domain, it is still possible to perform very fast subsequent solves, but this requires O(N log AT) storage. Numerical experiments indicate that the constants in these asymptotic estimates are quite moderate. For instance, to directly solve a system involving a 1 000 000 x 1 000 000 matrix to seven digits of accuracy takes about four minutes on a 2.8GHz desktop PC with 512Mb of memory. Additional solves beyond the first can be performed in 0.03 seconds (provided that only boundary data is involved). The proposed scheme is conceptually similar to a couple of recently developed methods for accelerating domain decomposition methods such as nested dissection. The original nested dissection algorithm reduces a problem defined on a two dimensional domain in the plane to a sequence of problems defined on one dimensional domains. These problems involve dense coefficient matrices, but the reduction in dimensionality results in a decrease in the cost of a direct solve from tofor a grid containing Ar points. Observed that these dense matrices in fact have internal structure, and that by exploiting this structure, it is possible to further reduce the computational cost. The scheme proposed here is similar to the schemes in that it relies on a combination of a dimension-reduction technique, and fast algorithms for structured matrices to solve the resulting sequence of dense problems. However, it uses a different technique for dimension reduction, and a much simpler format for working with structured matrices than previous schemes. Its principal advantage over larger parts of the computational domain. As a consequence, the scheme directly computes the solution operator that maps a boundary load to the solution on the boundary. Having access to this operator enables very fast solves in environments where a sequence of equations on the same computational grid are to be solved for a number of different boundary loads. The technique of hierarchical computation of Schur complements also appears to lead to improvements in robustness over competing methods.

Here we consider linear elliptic equations of second order, mainly the Laplace equation Solutions of the Laplace equation are called potential functions or harmonic functions. The Laplace equation is called also potential equation. The general elliptic equation for a scalar function, is where the matrixis real, symmetric and positive definite. If A is a constant matrix, then a transform to principal axis and stretching of axis leads to

Here we consider particular solutions of the Laplace equation inof the type whereis fixed and / is a function which we will determine such that u defines a solution if the Laplace equation. Set, then with constants Definition. Set. The function is called singularity function associated to the Laplace equation. Here isthe area of the n-dimensional unit sphere which is given by , where is the Gamma function. Definition. A function is called fundamental solution associated to the Laplace equation if andfor each fixed Remark. The fundamental solution 7 satisfies for each fixedthe relation In the language of distribution, this relation can be written by definition as whereis the Dirac distribution, which is called J-function.

Assumeis a connected domain.

of

(1) (2)

whereis given and continuous on Proposition 1. Assumeis bounded, then a solution to the Dirichlet problem is uniquely determined. Proof. Maximum principle. Remark. The previous result fails if we take away in the boundary condition (2) one point from the the boundary as the following example shows. Letbe the domain

Assumeis a solution of This problem has solutionsand, where Another example see an exercise. In contrast to this behaviour of the Laplace equation, one has uniqueness ifis replaced by the minimal surface equation Mixed boundary value problem - The Mixed boundary value problem (third boundary value problem) is to find a solut ionof

(4)

whereandare given and continuous onandare given and continuous on Proposition 2. Assume ft is bounded and sufficiently regular, then a solution to the mixed problem is uniquely determined in the class providedonandfor at least one point Proof Exercise. Hint: Multiply the differential equation by and integrate the result over

We consider the Dirichlet boundary value problem of distributional sense as follows

(5)

Here, the boundary datais a distribution on the boundaryof, andthe boundary condition in (5) is interpreted in the distributional sense that inas, where

(6)

for. Olofsson (2014) proved that, for parameter values, a function satisfies (5) if and only if it has the form of a Poisson type integral

(7)

where foris the standard Gamma function. If we take, then / is polyharmonic (or n-harmonic), where. Furthermore, Borichev and Hedenmalm (2014) proved that In particular, if, then / is harmonic. Forwith, the hyper geometric function is defined by the power series where (a)o = 1 andfor n = 1,2,... are the Pochhammer symbols. Obviously, for . In particular, for and, we have

(8)

For, Heinz (1959) and Colonna(1989) proved the following Schwarz-Pick type estimates on planar harmonic functions, which are the following. Theorem 1. For, letsatisfy (5) and , where M is a positive constant. Then, for

(9)

and

(10)

where

(11)

Let / be a harmonic mapping ofontowith. Heinz showed that, for, For the extensive discussion on the Heinz's inequality for real harmonic functions in high dimension. By using Theorem 1, we get a Heinz type inequality onas follows. Theorem 2. For, letsatisfying (5). Suppose that, and (a) If, then, for, (b) If, then, for, whereis given by (11). Theorem 3. Forletbe a solution to (1.1) with the series expansion of the form and , where M is a positive constant. Then, for,

(12)

and In particular, if, then the estimate of (12) is sharp and all the extreme functions are? where

In this section we describe a method for directly solving the linear system that relies on the sparsity pattern of the matrix only. In the absence of rounding errors, it would be exact. When the matrix A is of size. the method requires floating point operations and 0(N) memory. This makes the scheme significantly slower than well- knownschemes. (We mention

can straight-forwardly be accelerated to an or possibly evenscheme. Ordering the N points in the grid in the spiral pattern, the matrix A in equation Ax=b has the sparsity pattern for N = 100. We next partition the grid into m concentric squares and collect the nodes into index sets accordingly. In other words. For, we letdenote the submatrix of A formed by the inter section of therows with thecolumns. The linear system then takes on the block-tridiagonal form

(13)

where x and b have been partitioned accordingly. The sparsity and block pattern of (13) for m = 5. The blocked system of equations (13) can now easily be solved by eliminating the variablesone by one. Using the first, row to eliminatefrom the second row. we obtain the following system of equations for the variables:

(14)

where and This elimination process is continued row by row until we obtain the following equation for: Equation (15) is of sizeand is solved directly to obtain Thenis determined by solving the equation The remainingare computed analogously. To summarize the entire process: We note that while all matricesarc sparse, the matricesarc dense. This means that the cost of invertingin each step of the algorithm is. (The remaining matrix-matrix operations involve matrices that are diagonal or tri-diagonal and have negligible costs in comparison to the matrix inversion.) The total cost therefore satisfies

We have presented a scheme for rapidly performing direct solves on linear systems involving the large sparse matrices arising from the discretization of elliptic PDEs such as Laplace's equation, or the Helmholtz equation at low wave-numbers. The scheme presented typically achieves an asymptotic computational complexity of , with a constant saliently small that a direct solve of a linear system involving a million by million sparse coincident matrix can be performed in about four minutes. A.Borichev and H. Hedenmalm, Weighted integrability of polyharmonic functions, Adv. Math., 264(2014), 464–505. A.George, Nested dissection of a regular finite element mesh, SIAM J. on Numerical Analysis 10 (1973), 345{363. A.J. HoFFman, M. S. Martin, and D. J. Rose, Complexity bounds for regular ¯nite di®erence and finite element grids, SIAM J. Numer. Anal. 10 (1973), 364{369. A.Olofsson, Differential operators for a scale of Poisson type kernels in the unit disc, J. Anal. Math., 123 (2014), 227–249. E.Heinz, On one-to-one harmonic mappings, Pacific J. Math., 9(1959), 101–105. F.Colonna, The Bloch constant of bounded harmonic mappings, Indiana Univ. Math. J., 38 (1989), 829–840. H.H. Chen, The Schwarz-Pick lemma for planar harmonic mappings, Sci. China Math., 54(2011), 1101–1118. L.C. Evans and R. F. Gariepy, Measure Theory and Fine Properties of Functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, 1992. M.E. Taylor, Pseudodifferential operators. Princeton, New Jersey, 1981. P.G. Martinsson and V. Rokhlin, A fast direct solver for boundary integral equations in two dimensions, J. Comp. Phys. 205 (2005), no. 1, 1{23. P.Wilmott, S. Howison and J. Dewynne, The Mathematics of Financial Derivatives, A Student Introduction. Cambridge University Press, 1996. W.A. Strauss, Partial Differential equations. An Introduction. Second edition, Wiley-Interscience, 2008. German translation: Partielle Differentialgleichungen. Vieweg, 1995.