Browse Prior Art Database

WHAT IS THE COMPLE(ITY OF RELATED ELLIPTIC, PARABOLIC AND HYPERBOZIC PROBLEMS?

IP.com Disclosure Number: IPCOM000127975D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 26 page(s) / 49K

Publishing Venue

Software Patent Institute

Related People

Arthur G. Werschulz: AUTHOR [+3]

Abstract

Traub and Woziniakowski have dealt with the complexity of some simple partial differential equations. They chose three model problems, and showed that the parabolic problem consid-ered had significantly lower complexity than the elliptic problem, which in turn had significantly lower complexity from the hyperbolic problem considered. They asked whether this is true in general. We show that this is not the case. In fact, if L is a reasonably well-behaved elliptic operator, then the steady state equation Lu - f, the heat equation at u + Lu = f, and the wave equation a tt U + LU = f all have roughly the same worst-case complexity over f satisfying certain boundary conditions and having Sobolev r-norm bounded by unity.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 26

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

WHAT IS THE COMPLE(ITY OF RELATED ELLIPTIC, PARABOLIC AND HYPERBOZIC PROBLEMS?

Arthur G. Werschulz

Division of Science and Mathematics Fordham Univeksity/College at Lincoln Center New York, N.Y. 10023

and

Department of Computer Science Columbia University New York, N.Y. July, 1983

This research was supported in part by the National Science Foundation under Grants MCS- 8203271 and MCS-8303111.

C/C)U L9

Abstract

Traub and Woziniakowski have dealt with the complexity of some simple partial differential equations. They chose three model problems, and showed that the parabolic problem consid- ered had significantly lower complexity than the elliptic problem, which in turn had significantly lower complexity from the hyperbolic problem considered. They asked whether this is true in general. We show that this is not the case. In fact, if L is a reasonably well-behaved elliptic operator, then the steady state equation Lu - f, the heat equation at u + Lu = f, and the wave equation a tt U + LU = f all have roughly the same worst-case complexity over f satisfying certain boundary conditions and having Sobolev r-norm bounded by unity.

1. introduction.

This paper deals with the complexity of "related" elliptic, parabolic and hyperbolic partial differential equations. (in this introduction, we have to use~;terms such as complexity, minimal error, etc. without definition; they are defined rigorously later.)

Traub and Wozniakowski [6) have dealt with the complexity of three partial differential equations. The first problem was the heat equation on a thin rod of length 1T, with zero boundary data, the initial data was odd of period 2TT, having an r-th derivative whose L 2- norm was bounded by unity. They found if the solution was to be considered at a fixed time to.9 then the n th minimal error in the L 2- norm was

(Equation Omitted)

and the complexity of finding an C-approximation was

(Equation Omitted)

Columbia University Page 1 Dec 31, 1983

Page 2 of 26

WHAT IS THE COMPLE(ITY OF RELATED ELLIPTIC, PARABOLIC AND HYPERBOZIC PROBLEMS?

The second problem was Laplace's equation on a square of length rr in the x,y-plane, with zero boundary data on the west, south, and east sides of the square, the boundary data on the north side satisfied the same conditions as the initial data in the heat equation above. if the solution was to be considered along a line

(Equation Omitted)

then they

found the nth minimal L 2- error to behave asymptotically as

(Equation Omitted)

and the complexity of finding an C-approximation to

(Equation Omitted)

The third problem was AM ~ au, a first-order hyperbolic at ax problem, with initial data of period 2rr and mean value zero,

the L - norm of whose rth derivative was bounded by unity. 2 They considered the solution to

(Equation Omitted)

for a fixed

(Equation Omitted)

Here, the nth optimal L 2- error was

found to be

(Equation Omitted)

and the complexity of finding...