Sikorski, K
1997
Optimal Solution of Nonlinear Equations
Sikorski, K.
Oxford University Press, England, 1997. Funded in part by ACERC.
The purpose of this book is to provide an overview of optima computational methods for the solution of nonlinear algebraic equations, fixed points of contractive and noncontractive mappings, and for the computation of the topological degree. We analyze the worst case setting here. This means that for a given error criterion and tolerance e the methods guarantee to compute an e-approximation to the solution for every problem element in a given class F. The optimal methods solve the problem with the smallest possible cost that is called the e-complexity of the problem.
We study several classes of functions with special emphasis on tight complexity bounds and methods that are close to or achieve these bounds. In addition, pseudo codes and numerical tests of several methods are also exhibited.
1996
A Note on a Linear Time Algorithm for Constructing Adjacency Graphs of 3D FEA Data
Ueng, S.-K. and Sikorski, K.
Visual Computer, 12:1-6, 1996. Funded by ACERC.
In this paper, we present an algorithm for constructing adjacency graphs of 3D finite element analysis (FEA) data. Adjacency graphs are created to represent the connectivities of FEA data cells. They are used in most visualization methods for FEA data. We stress that in many engineering applications FEA data sets do not contain the adjacency information. This is opposite to computer-aided geometric design where, e.g., the winged edge geometrical representation is usually generated and utilized. By establishing intermediate data structures and using bin sorting, we develop an efficient algorithm for constructing such graphs. The total time complexity of the algorithm is linear in the number of data cells.
Efficient Streamline, Streamribbon, and Streamtube Constructions on Unstructured Grids
Ueng, S.-K.; Sikorski, K. and Ma, K.-L.
IEEE Transactions on Visualization and Computer Graphics, 2(2):100-108, 1996. Partially funded by ACERC.
Streamline construction is one of the most fundamental techniques for visualizing steady flow fields. Streamribbons and streamtubes are extensions for visualizing the rotation and the expansion of the flow. This paper presents efficient algorithms for constructing streamlines, streamribbons, and streamtubes on unstructured grids. A specialized Runge-Kutta method is developed to speed up the tracing of streamlines. Explicit solutions are derived for calculating the angular rotation rates of streamribbons and the radii of streamtubes. In order to simplify mathematical formulations and reduce computational costs, all calculations are carried out in the canonical coordinate system instead of the physical coordinate system. The resulting speed-up in overall performance helps explore large flow fields.
A Quasi-Monte Carlo Approach to Efficient 3-D Migration: Theory
Sikorski, K.
Geophysics, 1996/1997. Funded by Gas Research Institute.
A mathematical breakthrough was recently achieved in understanding the tractability of multidimensional integration using nearly optimal quasi-Monte Carlo methods. Inspired by the new mathematical insights, we have studied the feasibility of applying quasi-Monte Carlo methods to seismic imaging by 3-D pre-stack Kirchhoff migration. This earth imaging technique involves computing a large (10^9) number of 3- or 4-dimensional integrals. Our numerical studies show that nearly optimal quasi-Monte Carlo migration can produce the same or better quality erth images using only a small fraction (one fifth or less) of the data required by a conventional Kirchhoff migration.
The explanation is that an image migrated form a coarse quasi-random array of seismic data is less likely, on average, to be aliased than an image migrated form a regular array of data. In migrating these data, the geophones act as an incoherent arrangement of loudspeakers that broadcast the reflected wavefield back into the earth; the broadcast will produce reinforcement or cancellation of seismic energy at the , respectively, diffractor or grating lobe locations. Thus quasi-Monet Carlo migration contains an inherent anti-aliasing feature that tends to suppress migration artifacts without losing bandwidth. The penalty, however, is a decrease in the dynamic range of the migrated image compared to an image from a regular array of geophones. Our limited numerical results suggest that this loss in dynamic range is acceptable and so justifies the anti-aliasing benefits of migrating a random array of data.
Efficient Algorithms for 3-D Visualization and for Approximating Fixed Points
Sikorski, K.
Presented at Colloquium, Computer Science Department, Brigham Young University, February, 1996. Funded by Brigham Young University.
We review our recent research results in 3-D Visualization and the computation of fixed points of nonlinear equations.
The 3-D parallel volume-rendering algorithm is based on projection methods and master-slave model of distributed computation. We achieve almost linear speed-up in network implementation with a number of workstations.
The 3-D vector field algorithms for rendering streamlines, streamtubes and streamribbons are based on a new, specialized version of the RK-4 method, as well as on explicit solutions to differential equations describing angular rotation and expansion of the flow. The algorithms can render up to 100 streamlines (for 5000 time steps) with CPU of less than 2 sec. (IBM RS6000/560). This performance is achieved by applying specialized data structures and precomputation of essential interpolation functions on the unstructured tetrahedral data.
We describe Fixed Point Envelope (FPEN) and Fixed Point Ellipsoid (FPEL) algorithms for approximating fixed points of contractive functions. We proved the FPEN algorithm to be the most efficient method for univariate functions using the absolute and relative error criteria. In the multivariate case we developed the FPEL algorithm, which is much more efficient than the simple iteration for moderate dimension and mildly contractive functions. This algorithm is based on the ellipsoid construction of Kchachiyan for solving linear programming problems. For large dimension it is impossible to essentially improve the efficiency of the simple iteration.
1994
Selected Topics in Approximation and Computation
Sikorski, K.; Kowalski, M. and Stenger, F.
Oxford University Press, Oxford, England, 1995. Funded partially by IBM and ACERC.
This text covers classical basic results of approximation theory. It also obtains new developments in the theory of moments and Sinc approximation, as well as n-widths, s-numbers, and the relationship of these concepts to computational complexity. In addition, the text also contains several computational algorithms.
Chapter 1 covers basic concepts of classical approximation.
In Section 1.1, the classical and basic concepts of approximation theory are couched in the language of functional analysis. It is thus convenient to cover the concepts of existence and uniqueness of best approximation in a normed space setting.
A very important normed space from the point of both theory and application, in which to study best approximation is that of an inner product space. In this space it is convenient to study approximation in various polynomial settings, such as, via classical orthogonal polynomials, and via Cardinal, or sinc approximation. These concepts are covered in Section 1.2 of the text.
Concepts of approximation in the uniform norm are covered in Section 1.3. These concepts are also conveniently presented in a Banach space setting. Important examples from a classical standpoint include polynomial approximation with respect to the uniform norm.
Chapter 2 deals with spline methods of approximation.
Polynomials. Are historically the most popular tools of approximation, since they are easy to compute. However, a polynomial of high degree does not do a good job of approximating arbitrary given data, since it is then nearly always the case that the polynomial also has large over and undershoots between data points. On the other hand, splines, which are piecewise polynomials discussed in Chapter 2, are very convenient for approximating data, particularly data that is contaminated with noise. This is especially true of the practically important B-spines, which have variation-diminshing properties when used to approximate data, i.e., the total variation of the spline approximant is not more than that of the data. Thus splines provide particularly useful methods of approximation in the important areas of computer aided geometric design and for representing computer graphics displays.
Sinc methods discussed in Chapter 3 are ideal for approximating functions that may have singularities at end-points of an interval. Sline methods are ideal for approximation of data, and polynomial methods are ideal for approximating analytic functions that have no singularities on the interval of approximation. For example, if a function is analytic in a region containing an interval I, then we can achieve an O(exp{-b n}) error in a degree n polynomial approximation of the function in I, where b is some positive constant. This rapid exponential rate of decrease of the error reduces to a drastically slow O(n-b') rate in the case when the function has a singularity on I. Also, it turns out that Sinc methods provide simple to use accurate approximation tools for every operation of calculus, including the approximation of Hilbert transform, the approximation of derivatives, the approximation of definite and indefinite integration, the approximation and inversion of Laplace transforms, and the approximation of indefinite convolution integrals. While an O(exp{-b' n1/2}) error is also possible via spline approximation, by suitable choice of both the mesh and the degree of the spline on each subinterval, the constant b' in this exponential rate of convergence is usually not as large as the corresponding constant b for sinc approximation.
In Chapter 4 we present a family of simple rational functions, which make possible the explicit and arbitrarily accurate rational approximation of the filter, the step, and impulse functions.
Moment problems are conveniently discussed in the setting of approximation theory in Chapter 5. Included among the well known moment problems are the discrete and continuous moment problems named after Hausdorff, Stieltjes, and Hamburger, as well as the discrete and continuous trigonometric moment problems. We also include the Sinc moment problem, whose solution in the appropriate Sinc space is relatively easy, and devoid of the difficulties that one encounters using the usual monomial bases.
Chapter 6 deals with some rather "deep" concepts of approximation, namely, of n-widths and s-numbers. A historically first and practically important problem of approximation theory is to achieve a practically accurate approximation to a function f by e.g., a polynomial of a certain degree. Next, one might want to know the error of best approximation of the function f by polynomials of degree n. Following this, we could identify a class of functions F to which the function f to be approximated belongs, and we could then determine the maximum error of best approximation, as f is varied throughout F. Finally, we could vary out tools of approximation, i.e., the classes of n-dimensional subspaces, (e.g., not just polynomials) and so deduce the best method of approximation of functions in F. We are thus able to explore limits of approximability, a knowledge of which is both practically and theoretically worth while.
Chapter 7 discusses optimal methods of approximation, and optimal algorithms for general, nonlinear approximation problems. It relates approximability with the amount of work required to achieve a certain accuracy. These concepts are discussed in the general setting of normed spaces, and later, they are connected with splines, and also with the concepts of n-widths and s-numbers discussed in the previous chapter.
Chapter 8 illustrates applications of the approximation theory of the previous chapters. We discuss here the solution of Burgers' equation, the approximation of band-limited signals, and a nonlinear zero finding problem.
Each section of the text ends with a set of exercises. Each chapter closes with annotations including historical remarks that indicate the source of the material. The references follow afterwards.
Exercises are numbered from 1 to 180 globally throughout the text. Theorems, lemmas, corollaries, examples, and figures are numbered consecutively within each page. Therefore the notation Theorem 265.1 and Example 265.1 means first theorem and first example on page 265. There are no references to the literature inside of the text. All references are discussed in annotations to each chapter. Numbered formulas are almost eliminated to provide more structured text. In a few cases left they are numbered again according to the page system described above, i.e., formula 15.1 means first formula on page 15. We believe that the special format chosen will best serve the reader by providing more structured and self contained text.
Parallel Visualization of 3D Finite Element Analysis Data
Ueng, S.-K. and Sikorski, K.
SIAM Proceedings: Parallel Computation for Scientific Computing, 1994 (in press). Funded by ACERC.
In this paper, parallel volume-rendering algorithms for 3D finite element analysis (FEA) data are presented. These algorithms are designed for shared memory machines and distributed memory machines. Data space division and image space division are performed. The whole volume-rendering task is decomposed into sub-tasks called working units. Working units are dynamically assigned to processors. Data exchange and image composition are not necessary. Three kinds of images are produced: semi-transparent volume cloud, iso-surface and cross section images.
1993
Distributed Combustion Simulations
Sikorski, K.; Ma, K.-L.; Smith, P.J. and Adams, B.R.
Energy & Fuels, 7 (6):902-905, 1993. Funded by ACERC.
This paper reports research in progress. Two types of domain decomposition have been used in distributed computing with networked workstations for the numerical modeling of full-scale utility boilers. The numerical model is a three-dimensional combustion code that couples turbulent computational fluid dynamics with the chemical reaction process and the radiative heat transfer. Two approaches, here called microscale parallelism and macroscale parallelism, are proposed to study the intrinsic parallelism of typical combustion simulations. We describe the implementation of the microscale parallelism as well as its performance on networked workstations.
A Distributed 3D Navier-Stokes Solver in Express
Sikorski, K. and Ma, K.-L.
Energy & Fuels, 7 (6):1993, 897-902, funded by ACERC.
The Navier-Stokes equations are central to applied scientific research. The complete set of three-dimensional Navier-Stokes equations is very complex and thus requires a substantial amount of computer time as well as memory in order to obtain an accurate solution. The scalability in both processing power and memory space of distributed-memory parallel computers give promise of solving large-scale three-dimensional scientific problems based on these equations. In this paper, we describe the implementation and performance of a distributed three-dimensional Navier-Stokes solver in Parasoft's Express. We have run the solver on both the IBM Victor Computer (a 256-node transputer based system) and a token ring networked IBM RS/6000-520 workstation. Our test results demonstrate that distributed multiprocessing allows researchers to solve large-scale computational fluid dynamics problems and can improve their productivity with reducing turn around time.
An Ellipsoid Algorithm for the Computation of Fixed Points
Sikorski, K.; Tsay, C.W. and Wozniakowski, H.
Journal of Complexity, 9: 181-200, 1993. (Presented at NATO Advanced Studies Institute Conference, II Ciocco, Italy, September 1993. Also presented at the International Conference on Interval Methods, Lafayette, LA, February 1993.) Funded by IBM and ACERC.
We consider the problem of approximating fixed points of contractive functions with using the absolute error criterion. It was proven in (A.S. Nemirovsky, 1991, J. Complexity 7, 121-130) that it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. However, for a moderate dimension we exhibit a fixed-point ellipsoid algorithm which is much more efficient than the simple iteration for midly contractive functions. This algorithm is based on Khachiyan's construction of minimal volume ellipsoids used for solving linear programming.
1992
An Ellipsoid Algorithm for the Computation of Fixed Points
Sikorski, K.; Tsay, C.W. and Wozniakowski, H.
Journal of Complexity, 1992 (in press). Funded by University of Utah and ACERC.
We consider the problem of approximating fixed points of contractive functions with using the absolute error criterion. It was proven in [17] that it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. However, for a moderate dimension we exhibit a fixed-point ellipsoid algorithm which is much more efficient than the simple iteration for mildly contractive functions. This algorithm is based on Khachiyan's construction of minimal ellipsoids used for solving linear programming.
1991
A Distributed Solution and Visualization for 3-D Flow Simulation
Ma, K.-L. and Sikorski, K.
5th SIAM Conference on Parallel Processing for Scientific Computing, Houston, TX, March 1991. Funded by National Science Foundation and ACERC.
This paper describes a distributed algorithm for solving the 3-D unsteady compressible Navier-Stokes equations, and its implementation on the Inmos T800 transputer array, in particular, the IBM Victor Computer. Numerical experiments indicate that the algorithm offers the ultimate promise of supercomputer performance on relatively low-cost and highly scalable distributed memory parallel computers. In addition, we show the use of a visualization system that we have developed for observing flow structures and for verifying simulation results.
1990
A Distributed Algorithm for the Three-Dimensional Compressible Navier-Stokes Equations
Ma, K.-L. and Sikorski, K.
Transputer Research and Applications, 4:46, (D.L. Fielding, ed.), IOS Press, 1990. Funded by National Science Foundation and ACERC.
This paper describes a distributed algorithm for solving the three-dimensional unsteady compressible Navier-Stokes (N-S) equations, and its implementation on the IMS T800 transputer array. Numerical experiments indicate that the algorithm offers the ultimate promise of supercomputer performance on relatively low-cost distributed memory parallel computers. In addition, we have developed a scientific visualization system, which converts generic scientific data into graphical forms. This visualization system allows us to observe our simulations with ease.
Envelope and Ellipsoid Algorithms for the Computation of Fixed Points
Sikorski, K.
Conference for Solution of Systems Linear Equations: State of the Art, Italy, September 1990. Funded by the University of Utah and ACERC.
We consider the problem of approximating fixed points of contractive functions with using of the absolute error criterion. We describe two algorithms for solving this problem. The Fixed Point Envelope algorithm is the most efficient method for approximating fixed points in the univariate case. In the multivariate case it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. For a moderate dimension we exhibit a Fixed Point Ellipsoid algorithm which is much more efficient than the simple iteration for mildly contractive functions. This algorithm is based on the ellipsoid construction of Kchachiyan used for solving the linear programming problem. We list some numerical tests of the Ellipsoid algorithm.
1989
Three-Dimensional Modeling of Acoustic and Elastic Wave Propagation on Transputer Arrays
Sikorski, K.
North American Transputer Users Group Meeting, Salt Lake City, Utah, 1989. Funded by University of Utah.
We survey our recent experience with using parallel computers for modeling seismic wave propagation in the Salt Lake Basin. The computers under consideration are:
-
Distributed memory transputer array (we experimented with 16 to 96 processor machines, having from 0.25 to 2 Megabytes of memory per node), and
-
The Stellar GS 1000 graphics super workstation.
We have implemented a second-order finite difference algorithm with the first-order absorbing boundary conditions for the acoustic case and a staggered grid fourth-order finite difference algorithm for the elastic simulation. Our results suggest a linear speed-up with the increase in the number of nodes.
Sikorski, K
1997
Optimal Solution of Nonlinear Equations
Sikorski, K.
Oxford University Press, England, 1997. Funded in part by ACERC.
The purpose of this book is to provide an overview of optima computational methods for the solution of nonlinear algebraic equations, fixed points of contractive and noncontractive mappings, and for the computation of the topological degree. We analyze the worst case setting here. This means that for a given error criterion and tolerance e the methods guarantee to compute an e-approximation to the solution for every problem element in a given class F. The optimal methods solve the problem with the smallest possible cost that is called the e-complexity of the problem.
We study several classes of functions with special emphasis on tight complexity bounds and methods that are close to or achieve these bounds. In addition, pseudo codes and numerical tests of several methods are also exhibited.
1996
A Note on a Linear Time Algorithm for Constructing Adjacency Graphs of 3D FEA Data
Ueng, S.-K. and Sikorski, K.
Visual Computer, 12:1-6, 1996. Funded by ACERC.
In this paper, we present an algorithm for constructing adjacency graphs of 3D finite element analysis (FEA) data. Adjacency graphs are created to represent the connectivities of FEA data cells. They are used in most visualization methods for FEA data. We stress that in many engineering applications FEA data sets do not contain the adjacency information. This is opposite to computer-aided geometric design where, e.g., the winged edge geometrical representation is usually generated and utilized. By establishing intermediate data structures and using bin sorting, we develop an efficient algorithm for constructing such graphs. The total time complexity of the algorithm is linear in the number of data cells.
Efficient Streamline, Streamribbon, and Streamtube Constructions on Unstructured Grids
Ueng, S.-K.; Sikorski, K. and Ma, K.-L.
IEEE Transactions on Visualization and Computer Graphics, 2(2):100-108, 1996. Partially funded by ACERC.
Streamline construction is one of the most fundamental techniques for visualizing steady flow fields. Streamribbons and streamtubes are extensions for visualizing the rotation and the expansion of the flow. This paper presents efficient algorithms for constructing streamlines, streamribbons, and streamtubes on unstructured grids. A specialized Runge-Kutta method is developed to speed up the tracing of streamlines. Explicit solutions are derived for calculating the angular rotation rates of streamribbons and the radii of streamtubes. In order to simplify mathematical formulations and reduce computational costs, all calculations are carried out in the canonical coordinate system instead of the physical coordinate system. The resulting speed-up in overall performance helps explore large flow fields.
A Quasi-Monte Carlo Approach to Efficient 3-D Migration: Theory
Sikorski, K.
Geophysics, 1996/1997. Funded by Gas Research Institute.
A mathematical breakthrough was recently achieved in understanding the tractability of multidimensional integration using nearly optimal quasi-Monte Carlo methods. Inspired by the new mathematical insights, we have studied the feasibility of applying quasi-Monte Carlo methods to seismic imaging by 3-D pre-stack Kirchhoff migration. This earth imaging technique involves computing a large (10^9) number of 3- or 4-dimensional integrals. Our numerical studies show that nearly optimal quasi-Monte Carlo migration can produce the same or better quality erth images using only a small fraction (one fifth or less) of the data required by a conventional Kirchhoff migration.
The explanation is that an image migrated form a coarse quasi-random array of seismic data is less likely, on average, to be aliased than an image migrated form a regular array of data. In migrating these data, the geophones act as an incoherent arrangement of loudspeakers that broadcast the reflected wavefield back into the earth; the broadcast will produce reinforcement or cancellation of seismic energy at the , respectively, diffractor or grating lobe locations. Thus quasi-Monet Carlo migration contains an inherent anti-aliasing feature that tends to suppress migration artifacts without losing bandwidth. The penalty, however, is a decrease in the dynamic range of the migrated image compared to an image from a regular array of geophones. Our limited numerical results suggest that this loss in dynamic range is acceptable and so justifies the anti-aliasing benefits of migrating a random array of data.
Efficient Algorithms for 3-D Visualization and for Approximating Fixed Points
Sikorski, K.
Presented at Colloquium, Computer Science Department, Brigham Young University, February, 1996. Funded by Brigham Young University.
We review our recent research results in 3-D Visualization and the computation of fixed points of nonlinear equations.
The 3-D parallel volume-rendering algorithm is based on projection methods and master-slave model of distributed computation. We achieve almost linear speed-up in network implementation with a number of workstations.
The 3-D vector field algorithms for rendering streamlines, streamtubes and streamribbons are based on a new, specialized version of the RK-4 method, as well as on explicit solutions to differential equations describing angular rotation and expansion of the flow. The algorithms can render up to 100 streamlines (for 5000 time steps) with CPU of less than 2 sec. (IBM RS6000/560). This performance is achieved by applying specialized data structures and precomputation of essential interpolation functions on the unstructured tetrahedral data.
We describe Fixed Point Envelope (FPEN) and Fixed Point Ellipsoid (FPEL) algorithms for approximating fixed points of contractive functions. We proved the FPEN algorithm to be the most efficient method for univariate functions using the absolute and relative error criteria. In the multivariate case we developed the FPEL algorithm, which is much more efficient than the simple iteration for moderate dimension and mildly contractive functions. This algorithm is based on the ellipsoid construction of Kchachiyan for solving linear programming problems. For large dimension it is impossible to essentially improve the efficiency of the simple iteration.
1994
Selected Topics in Approximation and Computation
Sikorski, K.; Kowalski, M. and Stenger, F.
Oxford University Press, Oxford, England, 1995. Funded partially by IBM and ACERC.
This text covers classical basic results of approximation theory. It also obtains new developments in the theory of moments and Sinc approximation, as well as n-widths, s-numbers, and the relationship of these concepts to computational complexity. In addition, the text also contains several computational algorithms.
Chapter 1 covers basic concepts of classical approximation.
In Section 1.1, the classical and basic concepts of approximation theory are couched in the language of functional analysis. It is thus convenient to cover the concepts of existence and uniqueness of best approximation in a normed space setting.
A very important normed space from the point of both theory and application, in which to study best approximation is that of an inner product space. In this space it is convenient to study approximation in various polynomial settings, such as, via classical orthogonal polynomials, and via Cardinal, or sinc approximation. These concepts are covered in Section 1.2 of the text.
Concepts of approximation in the uniform norm are covered in Section 1.3. These concepts are also conveniently presented in a Banach space setting. Important examples from a classical standpoint include polynomial approximation with respect to the uniform norm.
Chapter 2 deals with spline methods of approximation.
Polynomials. Are historically the most popular tools of approximation, since they are easy to compute. However, a polynomial of high degree does not do a good job of approximating arbitrary given data, since it is then nearly always the case that the polynomial also has large over and undershoots between data points. On the other hand, splines, which are piecewise polynomials discussed in Chapter 2, are very convenient for approximating data, particularly data that is contaminated with noise. This is especially true of the practically important B-spines, which have variation-diminshing properties when used to approximate data, i.e., the total variation of the spline approximant is not more than that of the data. Thus splines provide particularly useful methods of approximation in the important areas of computer aided geometric design and for representing computer graphics displays.
Sinc methods discussed in Chapter 3 are ideal for approximating functions that may have singularities at end-points of an interval. Sline methods are ideal for approximation of data, and polynomial methods are ideal for approximating analytic functions that have no singularities on the interval of approximation. For example, if a function is analytic in a region containing an interval I, then we can achieve an O(exp{-b n}) error in a degree n polynomial approximation of the function in I, where b is some positive constant. This rapid exponential rate of decrease of the error reduces to a drastically slow O(n-b') rate in the case when the function has a singularity on I. Also, it turns out that Sinc methods provide simple to use accurate approximation tools for every operation of calculus, including the approximation of Hilbert transform, the approximation of derivatives, the approximation of definite and indefinite integration, the approximation and inversion of Laplace transforms, and the approximation of indefinite convolution integrals. While an O(exp{-b' n1/2}) error is also possible via spline approximation, by suitable choice of both the mesh and the degree of the spline on each subinterval, the constant b' in this exponential rate of convergence is usually not as large as the corresponding constant b for sinc approximation.
In Chapter 4 we present a family of simple rational functions, which make possible the explicit and arbitrarily accurate rational approximation of the filter, the step, and impulse functions.
Moment problems are conveniently discussed in the setting of approximation theory in Chapter 5. Included among the well known moment problems are the discrete and continuous moment problems named after Hausdorff, Stieltjes, and Hamburger, as well as the discrete and continuous trigonometric moment problems. We also include the Sinc moment problem, whose solution in the appropriate Sinc space is relatively easy, and devoid of the difficulties that one encounters using the usual monomial bases.
Chapter 6 deals with some rather "deep" concepts of approximation, namely, of n-widths and s-numbers. A historically first and practically important problem of approximation theory is to achieve a practically accurate approximation to a function f by e.g., a polynomial of a certain degree. Next, one might want to know the error of best approximation of the function f by polynomials of degree n. Following this, we could identify a class of functions F to which the function f to be approximated belongs, and we could then determine the maximum error of best approximation, as f is varied throughout F. Finally, we could vary out tools of approximation, i.e., the classes of n-dimensional subspaces, (e.g., not just polynomials) and so deduce the best method of approximation of functions in F. We are thus able to explore limits of approximability, a knowledge of which is both practically and theoretically worth while.
Chapter 7 discusses optimal methods of approximation, and optimal algorithms for general, nonlinear approximation problems. It relates approximability with the amount of work required to achieve a certain accuracy. These concepts are discussed in the general setting of normed spaces, and later, they are connected with splines, and also with the concepts of n-widths and s-numbers discussed in the previous chapter.
Chapter 8 illustrates applications of the approximation theory of the previous chapters. We discuss here the solution of Burgers' equation, the approximation of band-limited signals, and a nonlinear zero finding problem.
Each section of the text ends with a set of exercises. Each chapter closes with annotations including historical remarks that indicate the source of the material. The references follow afterwards.
Exercises are numbered from 1 to 180 globally throughout the text. Theorems, lemmas, corollaries, examples, and figures are numbered consecutively within each page. Therefore the notation Theorem 265.1 and Example 265.1 means first theorem and first example on page 265. There are no references to the literature inside of the text. All references are discussed in annotations to each chapter. Numbered formulas are almost eliminated to provide more structured text. In a few cases left they are numbered again according to the page system described above, i.e., formula 15.1 means first formula on page 15. We believe that the special format chosen will best serve the reader by providing more structured and self contained text.
Parallel Visualization of 3D Finite Element Analysis Data
Ueng, S.-K. and Sikorski, K.
SIAM Proceedings: Parallel Computation for Scientific Computing, 1994 (in press). Funded by ACERC.
In this paper, parallel volume-rendering algorithms for 3D finite element analysis (FEA) data are presented. These algorithms are designed for shared memory machines and distributed memory machines. Data space division and image space division are performed. The whole volume-rendering task is decomposed into sub-tasks called working units. Working units are dynamically assigned to processors. Data exchange and image composition are not necessary. Three kinds of images are produced: semi-transparent volume cloud, iso-surface and cross section images.
1993
Distributed Combustion Simulations
Sikorski, K.; Ma, K.-L.; Smith, P.J. and Adams, B.R.
Energy & Fuels, 7 (6):902-905, 1993. Funded by ACERC.
This paper reports research in progress. Two types of domain decomposition have been used in distributed computing with networked workstations for the numerical modeling of full-scale utility boilers. The numerical model is a three-dimensional combustion code that couples turbulent computational fluid dynamics with the chemical reaction process and the radiative heat transfer. Two approaches, here called microscale parallelism and macroscale parallelism, are proposed to study the intrinsic parallelism of typical combustion simulations. We describe the implementation of the microscale parallelism as well as its performance on networked workstations.
A Distributed 3D Navier-Stokes Solver in Express
Sikorski, K. and Ma, K.-L.
Energy & Fuels, 7 (6):1993, 897-902, funded by ACERC.
The Navier-Stokes equations are central to applied scientific research. The complete set of three-dimensional Navier-Stokes equations is very complex and thus requires a substantial amount of computer time as well as memory in order to obtain an accurate solution. The scalability in both processing power and memory space of distributed-memory parallel computers give promise of solving large-scale three-dimensional scientific problems based on these equations. In this paper, we describe the implementation and performance of a distributed three-dimensional Navier-Stokes solver in Parasoft's Express. We have run the solver on both the IBM Victor Computer (a 256-node transputer based system) and a token ring networked IBM RS/6000-520 workstation. Our test results demonstrate that distributed multiprocessing allows researchers to solve large-scale computational fluid dynamics problems and can improve their productivity with reducing turn around time.
An Ellipsoid Algorithm for the Computation of Fixed Points
Sikorski, K.; Tsay, C.W. and Wozniakowski, H.
Journal of Complexity, 9: 181-200, 1993. (Presented at NATO Advanced Studies Institute Conference, II Ciocco, Italy, September 1993. Also presented at the International Conference on Interval Methods, Lafayette, LA, February 1993.) Funded by IBM and ACERC.
We consider the problem of approximating fixed points of contractive functions with using the absolute error criterion. It was proven in (A.S. Nemirovsky, 1991, J. Complexity 7, 121-130) that it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. However, for a moderate dimension we exhibit a fixed-point ellipsoid algorithm which is much more efficient than the simple iteration for midly contractive functions. This algorithm is based on Khachiyan's construction of minimal volume ellipsoids used for solving linear programming.
1992
An Ellipsoid Algorithm for the Computation of Fixed Points
Sikorski, K.; Tsay, C.W. and Wozniakowski, H.
Journal of Complexity, 1992 (in press). Funded by University of Utah and ACERC.
We consider the problem of approximating fixed points of contractive functions with using the absolute error criterion. It was proven in [17] that it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. However, for a moderate dimension we exhibit a fixed-point ellipsoid algorithm which is much more efficient than the simple iteration for mildly contractive functions. This algorithm is based on Khachiyan's construction of minimal ellipsoids used for solving linear programming.
1991
A Distributed Solution and Visualization for 3-D Flow Simulation
Ma, K.-L. and Sikorski, K.
5th SIAM Conference on Parallel Processing for Scientific Computing, Houston, TX, March 1991. Funded by National Science Foundation and ACERC.
This paper describes a distributed algorithm for solving the 3-D unsteady compressible Navier-Stokes equations, and its implementation on the Inmos T800 transputer array, in particular, the IBM Victor Computer. Numerical experiments indicate that the algorithm offers the ultimate promise of supercomputer performance on relatively low-cost and highly scalable distributed memory parallel computers. In addition, we show the use of a visualization system that we have developed for observing flow structures and for verifying simulation results.
1990
A Distributed Algorithm for the Three-Dimensional Compressible Navier-Stokes Equations
Ma, K.-L. and Sikorski, K.
Transputer Research and Applications, 4:46, (D.L. Fielding, ed.), IOS Press, 1990. Funded by National Science Foundation and ACERC.
This paper describes a distributed algorithm for solving the three-dimensional unsteady compressible Navier-Stokes (N-S) equations, and its implementation on the IMS T800 transputer array. Numerical experiments indicate that the algorithm offers the ultimate promise of supercomputer performance on relatively low-cost distributed memory parallel computers. In addition, we have developed a scientific visualization system, which converts generic scientific data into graphical forms. This visualization system allows us to observe our simulations with ease.
Envelope and Ellipsoid Algorithms for the Computation of Fixed Points
Sikorski, K.
Conference for Solution of Systems Linear Equations: State of the Art, Italy, September 1990. Funded by the University of Utah and ACERC.
We consider the problem of approximating fixed points of contractive functions with using of the absolute error criterion. We describe two algorithms for solving this problem. The Fixed Point Envelope algorithm is the most efficient method for approximating fixed points in the univariate case. In the multivariate case it is impossible to essentially improve the efficiency of the simple iteration whenever the dimension of the domain of contractive functions is large. For a moderate dimension we exhibit a Fixed Point Ellipsoid algorithm which is much more efficient than the simple iteration for mildly contractive functions. This algorithm is based on the ellipsoid construction of Kchachiyan used for solving the linear programming problem. We list some numerical tests of the Ellipsoid algorithm.
1989
Three-Dimensional Modeling of Acoustic and Elastic Wave Propagation on Transputer Arrays
Sikorski, K.
North American Transputer Users Group Meeting, Salt Lake City, Utah, 1989. Funded by University of Utah.
We survey our recent experience with using parallel computers for modeling seismic wave propagation in the Salt Lake Basin. The computers under consideration are:
-
Distributed memory transputer array (we experimented with 16 to 96 processor machines, having from 0.25 to 2 Megabytes of memory per node), and
-
The Stellar GS 1000 graphics super workstation.
We have implemented a second-order finite difference algorithm with the first-order absorbing boundary conditions for the acoustic case and a staggered grid fourth-order finite difference algorithm for the elastic simulation. Our results suggest a linear speed-up with the increase in the number of nodes.