Yuan Xu - US grants

Xu 9302721 This project concerns applications of the theory of special functions to problems of quadrature. Quadrature is a term given to methods of integration, especially numerical. It has been highly developed in one dimension with tools such as the Gaussian quadrature formula. The present work seeks to carry out numerical integration through methods of cubature in several dimensions. The generalization is far from straightforward. The quadratures and cubatures require knowledge of orthogonal polynomials, particularly with common roots. In the multidimensional case, orthogonal polynomials with common roots were thought to be rare. However recent work now establishes that there are many Gaussian cubatures. The purpose of this work is to use the newly developed tools to investigate this topic further. Several goals are established. First, to obtain applicable characterization of Gaussian cubatures, then to construct new efficient numerical integration formulae. Work will also be done applying the cubature formulae to the theory of interpolation in several variables. The use of orthogonal polynomials in numerical integration provides formulas which are optimal in the sense of being exact for polynomials of the highest possible degree. As such they provide good approximations to integrals of smooth functions. The recent breakthroughs in carrying these ideas over to several variables holds out the possibility of a robust multivariate cubature and approximation theory in several variables, a subject still in its infancy. ***

9500532 Xu The purpose of this research project is to study the common zeros of polynomials in several variables in connection with the numerical approximation to integrals in several variables. Compared to the case of one variable, zeros of polynomials in several variables and high dimensional quadrature formulae are much more difficult and the results have been scattered. Recently the a new approach was used to study the topic and showed that positive high dimensional quadrature formulae can be characterized through the existence of real common zeros of certain set of quasi-orthogonal polynomials; necessary and sufficient conditions for the existence of such zeros were also obtained, which are given in terms of certain nonlinear matrix equations. The project will involve the continuation of this study and will use this approach to conduct a systematic study of this topic. It is very likely that the approach will enable one to tackle several fundamental questions, such as the connection to moment problems in several variables which may lead to an analytic characterization of common zeros, structure of minimal and ``near'' minimal cubature formulae, and construction of new efficient numerical integration formulae. The goal is to establish a unified theory for high dimensional numerical integration formulae based on the common zeros of quasi-orthogonal polynomials. The outcome of the project will help in understanding the structure of high dimensional numerical integration formulae and the structure of the common zeros of polynomials. The information will be very useful in finding new formulae for practical evaluation of high dimensional integrals, which is one of the essential questions in numerical analysis and is often taken as a test problem in high speed computing; it can also be very useful in constructing formulae with special properties, for example, the equal-weight formulae on spheres, which have applications in coding theory. The project is also motivated by the potential a pplications of the outcome in other areas of numerical mathematics, such as orthogonal polynomials in several variables and interpolation by polynomials which are basic tools for data fitting and surface reconstruction.

Abstract: The project continues an ongoing program, the aim of which is to
establish a workable theory for orthogonal polynomials (OP) in several
variables and use the knowledge to construct cubature formulae (CF), synonym
for higher dimensional numerical integration formulae. A general framework
has been developed by the P.I. in the first phase of this program, including
an extensive theory of OP in several variables based on a new vector-matrix
notation and a systematic study of the relation between CF and the common
zeros of (quasi-)OP. The main focus of this project is on OP and CF on the
unit sphere, on the unit ball and on the standard simplex of the Euclidean
space. The starting point is a recent observation made by the P.I. that
orthogonal structures on these domains are closely related, which has led to
new understanding about OP on these classical domains and to a powerful new
method for constructing CF. Special attention will be given to the structure
of OP and CF that are invariant under certain groups, such as octahedral group
or symmetric group of the simplex, which has a close relation to the recent
development of h-harmonics associated to the reflection groups.

Cubature formulae and orthogonal polynomials in several variables have
fruitful connections with many branches of applied mathematics such as
numerical integration, approximation, coding theory, data fitting, numerical
solution of differential equation, finite element methods to name a few. CF
itself is essential for practical evaluation of high dimensional integrals,
which is one of the basic questions in numerical analysis and is often taken
as a test problem in high speed computing. The present project seeks new
understanding of the nature of CF and OP in several variables. Its aim is to
determine the precise relationship between orthogonal structures on the sphere,
the ball, and the simplex, especially analytic relations which will lead to new
progress on convergence of the orthogonal expansion, and to develop practical
method that will yield new effective numerical integration formulae on these
domains, especially on the unit sphere.

DMS Award Abstract
Award #: 0201669
PI: Xu, Yuan
Institution: University of Oregon
Program: Applied Mathematics
Program Manager: Catherine Mavriplis

Title: Cubature Formulae and Orthogonal Polynomials in Several Variables

The aim of this project is to study various aspects of cubature formulae (CF), synonym for higher dimensional numerical integration formulae, and orthogonal polynomials of several variables (OP). The project calls for a study of cubature formula from an algebraic point of view as well as new constrction method, such as through studying of polynomial interpolation in several variables. It also proposes to investigate further properties of OP with respect to weight functions on various regular domains, such as the cube, the ball, the simplex and the sphere. The aim is to uncover further hidden properties of CF and OP, and to find closed formulae and explicit construction, so that further theoretic results and methods with practical implication can be built upon.

Cubature Formulae (CF) and Orthogonal Polynomials (OP) of several variables have fruitful connections with many branches of applied mathematics such as numerical integration, approximation, coding theory, data fitting, combinatorics and statistics, to name a few, as well as with areas such as harmonic analysis, group representation, computational algebraic geometry and differential equation. CF itself is essential for practical evaluation of high dimensional integrals, which is one of the basic questions in numerical analysis and is often taken as a test problem in high speed computing. The proposed project seeks new understanding in the nature of CF and OP in several variables, and it aims at workable results that have practical implications, such as new method for constructing CF.

Date: June 18, 2002

Computed Tomography (CT) offers a non-invasive method for two-dimensional cross-sectional or three-dimensional imaging of an object. In a typical CT application, the distribution of the attenuation coefficient through a body from measurements of x-ray transmission is estimated and used to reconstruct an image of the object. The algorithm currently used to generate an image from x-ray measurement data is the filtered backprojection (FBP) method, which has been the primary method for the past thirty years. The FBP method, based mathematically on the Fourier transform and convolution, is effective, but it also has a number of inherent drawbacks. The main objective of this project is to provide new algorithms, based on a new mathematical approach, that will be more effective, produce images of better quality, and use lower x-ray dose. The new algorithm is called OPED, as it is based on orthogonal polynomial expansions on the disk. The project will explore the mathematical properties of the OPED algorithms, such as convergence, speed, and resolution, with emphasis on applicability. It will also study the compatibility of the new algorithm and the scanning geometry of the x-ray input. Furthermore, it aims at extending the algorithms from two-dimensional to three-dimensional images.





Computer tomography is an important tool in biomedical research and has been widely used in diagnostic medicine in clinics and hospitals. It has also found widespread applications in many other scientific fields, including physics, chemistry, astronomy, geophysics, and biological sciences. The purpose of the project is to provide improved algorithms for image reconstruction in computed tomography. The goal is to develop algorithms that will produce images of high resolution with few artifacts in reasonable time and use relatively low x-ray dose to lower the risk of biological damage caused by excessive x-ray exposure. Such an algorithm will make the use of x-ray CT more effective in diagnostic medicine.

Xu
DMS-1106113

The principal investigator studies cubature rules, which are numerical integration formulas for higher dimensional integrals, and approximation of functions on regular domains such as cubes, balls, spheres and simplexes. The project combines several topics: numerical analysis, discrete Fourier analysis, orthogonal polynomials, and approximation theory. Two approaches are emphasized. The first approach is based on a connection between cubature rules and discrete Fourier analysis with translation tiling. The approach allows one to study, in several stages, cubature rules and interpolation by exponential functions on the fundamental domain of the translation tiling, by trigonometric functions on the fundamental simplex of the domain, and by algebraic polynomials on corresponding domains, and it yields results on cubature rules, interpolation, orthogonal polynomials and approximation. The second approach starts with a characterization of best approximation by polynomials on the sphere and on the ball in terms of the smoothness of the functions being approximated, while the smoothness is measured by the differences of the function values in Euler angles. This line of work is based on recent results of the investigator and his collaborators that for some problems it is necessary to work with these angles, even though their number is much larger than the dimension.

Cubature rules, which are multidimensional numerical integration formulas, and approximation on regular domains in higher dimensional spaces are fundamental tools in a variety of applications, because most integrals can only be evaluated numerically and very few problems can be evaluated exactly. At the current stage, in contrast to the situation in one dimension, many fundamental problems in these two areas have not been resolved, despite increasing need for them in applications. The project aims at finding new methods to construct numerically efficient algorithms, such as accurate cubature rules with fewer nodes, fast discrete Fourier transforms, and approximation operators on regular domains such as cubes, balls, spheres and simplexes. The algorithms have applications in scientific computing, imaging, statistics, and geosciences.

This research project is concerned with the study of approximations of functions of several variables by families of simpler, polynomial functions (and related questions) in the setting of Sobolev spaces, which are abstract mathematical function spaces originally developed to study problems in mathematical physics and which are utilized today in a number of scientific computing settings. A truly complex system or problem is often intractable, and we often need to find an approximation that is more manageable. Approximation methods on domains in higher dimensional spaces are good examples of this principle, and they are crucial in many problems in applied mathematics. In contrast to one dimension, many challenging problems in higher dimensions that are of fundamental importance are not resolved. The Principal Investigator will study several problems on approximation and orthogonality in Sobolev spaces that rely on new connections and ideas revealed only recently. The project aims at both theoretical understanding and construction of new approximation methods, and the work has the potential to impact scientific computing, numerical analysis, statistics, and geoscience.

The Principal Investigator will study approximation and orthogonality in Sobolev spaces on regular domains, such as cubes, balls, spheres, and simplexes. The project combines several research topics: approximation theory, Fourier analysis, numerical analysis, and orthogonal polynomials. One of the main problems originates from the area of spectral methods for the numerical solution of partial differential equations. Through recent work of the Principal Investigator and collaborators, it has become increasingly clear that understanding orthogonality in Sobolev spaces is crucial for approximation and computation in Sobolev spaces. This research will be based on recent progress in characterization of best approximation by polynomials on the unit sphere and on the unit ball, in Sobolev orthogonal polynomials, and in spectral approximation. The project is expected to lead to new scientific computational methods and new algorithms.