Browse Prior Art Database

DOES INCREASED REGULARITY LOWER COMPLEXITY?

IP.com Disclosure Number: IPCOM000127968D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 38 page(s) / 67K

Publishing Venue

Software Patent Institute

Related People

Arthur G. Werschulz: AUTHOR [+3]

Abstract

Intuitively, the more regular a problem, the easier it should be to solve. Examples drawn from ordinary and partial differential equations, as well as from approximation, support the intuition. Traub and Wozjniakowski conjectured that this is always the case. In this paper, we study linear problems. We prove a weak form of the conjecture, and show that this weak form cannot be strengthened. To do this, we consider what happens to the optimal error when regularity is increased. If regularity is measured by a Sobolev norm, increasing the regularity improves the optimal error, which allows us to establish the conjecture in the normed case. On the other hand, if regularity is measured by a Sobolev seminorm, it is no longer true that increasing the regularity improves the optimal error. However, a "shifted" version of this statement holds, which enables us to establish the conjecture in the semi-normed case.

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

Page 1 of 38

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

DOES INCREASED REGULARITY LOWER COMPLEXITY?

by

Arthur G. Werschulz

Division of Science and Mathematics Fordham University/College at Lincoln Center New York, NY 10023

and

Department of Computer Science Columbia University New York, NY 10027

December, 1982

Revision of "On the Role of Increased Regularity in Analytic Computational Complexity," Mathematics Research Report 81-7, University of Maryland Baltimore County, Catonsville, MD 21228 (October, 1981)

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

Abstract

Intuitively, the more regular a problem, the easier it should be to solve. Examples drawn from ordinary and partial differential equations, as well as from approximation, support the intuition. Traub and Wozjniakowski conjectured that this is always the case. In this paper, we study linear problems. We prove a weak form of the conjecture, and show that this weak form cannot be strengthened. To do this, we consider what happens to the optimal error when regularity is increased. If regularity is measured by a Sobolev norm, increasing the regularity improves the optimal error, which allows us to establish the conjecture in the normed case. On the other hand, if regularity is measured by a Sobolev seminorm, it is no longer true that increasing the regularity improves the optimal error. However, a "shifted" version of this statement holds, which enables us to establish the conjecture in the semi-normed case.

1. Introduction

We investigate the rel ation between regularity and complexity. In this Introduction, we use words such as algorithm, information, cardinality, and regularity without definition. They are rigorously defined later.

Based on a variety of examples, Traub and Wozniakowski [61 conjectured that, in general, as theregularity of a class of problem elements increases, the complexity decreases. in this paper, we consider linear problems. We measure regularity by a Sobolev norm or seminorm. We prove a weak form of this conjecture, and show that no stronger statement is possible.

To fix ideas, we consider several examples.

Columbia University Page 1 Dec 31, 1982

Page 2 of 38

DOES INCREASED REGULARITY LOWER COMPLEXITY?

Example 1.1. Consider the solution of the two-point boundary-value problem

(Equation Omitted)

Consider an algorithm 0 using information of cardinality at most n, and define the error e(~p) to be the worst-case error (in the H 1- sense) taken over all f satisfying (1.2). Let (1.3)

(Equation Omitted)

be the minimal error of all such n-evaluation algorithms cp whose input functions f satisfy (1.2). In [7], we showed that

(1.4)

(Equation Omitted)

where we use Knuth's 9-notation

(1.5)

(Equation Omitted)

If comp(e,r) denotes the complexity of finding an e-approximation, then (1.4) implies

(1.6)

(Equation Omitted)

The next four examples are taken from [6]. In these examples, the data consisted of all f E...