Abstract

In nonlinear approximation we seek ways to approximate complicated functions by simpler functions using methods that depend nonlinearly on the function being approximated. Recently, a particular kind of nonlinear approximation, namely greedy approximation has attracted a lot of attention in both theoretical and applied settings. Greedy type algorithms have proven to be very useful in various applications such as image compression, signal processing, design of neural networks, and the numerical solution of nonlinear partial differential equations. A theory of greedy approximation is now emerging. Some fundamental convergence results have already been established and many fundamental problems remain unsolved. In this survey we place emphasis on the study of the efficiency of greedy algorithms with regards to redundant systems (dictionaries). Redundancy, on the one hand, offers much promise for greater efficiency in terms of the rate of approximation. On the other hand, it gives rise to highly nontrivial theoretical and practical problems. We note that there is solid justification for the importance of redundant systems in both theoretical questions and practical applications. This survey is a continuation of the survey Temlyakov (2003a) on nonlinear approximations. Here we concentrate on more recent results on greedy approximation.

Introduction

In the last decade we have seen successes in the study of nonlinear approximation (see the surveys DeVore (1998) and Temlyakov (2003a)). This study was motivated by numerous applications. Nonlinear approximation is important in applications because of its efficiency.

Abstract

These pages summarize some results on the efficiency of polynomial equation solving. We focus on semantic algorithms, i.e., algorithms whose running time depends on some intrinsic/semantic invariant associated with the input data. Both computer algebra and numerical analysis algorithms are discussed. We show a probabilistic and positive answer to Smale's 17th problem. Estimates of the probability distribution of the condition number of singular complex matrices are also exhibited.

Introduction

These pages summarize some results on upper and lower complexity bounds in Elimination Theory. They are a revision of the program stated in Pardo (1995).

We focus on Efficient Polynomial Equation Solving. This is one of the challenges in the recent history of Computational Mathematics. Two main frameworks in scientific computing deal with this problem. Following different approaches, symbolic/algebraic computing and numerical analysis developed their own techniques for solving polynomial equations. We survey statements of both approaches. New results are contained in Sections 1.4 and 1.5.

Multivariate Polynomial Equation Solving is a central topic both in Computational Mathematics and Computational Algebraic Geometry (Elimination Theory in nineteenth century terminology). Its origin goes back to work of Sturm, Hermite, Cayley, and Sylvester, among others. Elimination Theory consists of the preparation of input data (polynomial equations and inequalities) to answer questions involving quantifiers. This approach also underlies Kronecker (1882), Hilbert (1890) and further developments in Algebraic Geometry.

Introduction

Although Java first gained fame with applets in Web browsers and then became a popular tool for creating large enterprise services, the developers of Java originally intended it for embedded applications in consumer devices such as TV remote controls and Personal Data Assistants (see Chapter 1). The term “embedded” generally refers to encapsulating a processor into a device, along with programs stored in non-volatile memory, to provide services and features specific to that device. Microcontrollers, for example, are the most common type of embedded processors.

By embedded Java we refer to a device that contains either a conventional processor running a JVM or a special type of processor that either directly executes Java bytecodes or assists a conventional processor with executing bytecodes. The motivations for device designers to embed Java depend on the particular device, but, in general, Java provides flexibility, interactivity, networking, portability, and fast development of the software for embedded projects.

Today several types of commercial devices come with Java built into them. As mentioned in Chapter 1, over 600 million JavaCards have been sold around the world as of mid-2004, and several hundred cell phone models include Java.

Embedded applications typically must deal with very limited resources. A full-blown J2SE application on a desktop with a Swing graphical interface might require several megabytes of RAM.

Introduction

In Chapter 6 we presented the basic techniques for loading image files into applets and applications. We used instances of the Image class to hold images and invoked the drawImage() method in the Graphics class to display them. In this chapter we explore further the image handling and processing capabilities of Java.

In the first few sections we look in greater detail at the Image class and introduce its BufferedImage subclass, which offers many useful features. We discuss how to monitor the loading of images, how to scale image displays, how to create images, and how to save images to files.

We then switch to topics related to image processing. We show how to gain access to the pixels of an image, how to modify them, how to make an image from a pixel array, and how to use these techniques to create animations. We then discuss the standard filters provided with Java 2D and also give an example of a custom filter.

We give only a brief overview of the wide range of image tools available with Java. The classes mentioned here, for example, hold many overloaded constructors and methods that provide many options. See the Java 2 API Specifications for thorough descriptions of the classes. Also, see the book by Knudsen [1] and the other resources for in-depth discussions of images in Java [2, 3].

Introduction

In Part I of this book and Web Course we tried to provide an introduction to the essential elements of the Java language that allow you to begin creating useful programs in short order. In this chapter we discuss several practical techniques that will expand the capabilities of your programs. We begin with a discussion of how to print your graphics displays and then discuss several user interface features such as cursor icons and popup menus, handling keystrokes, and audio. We also review various ways to improve the speed of Java programs.

Printing

Java 1.1 provided the capability to print what is displayed on a Java component [1]. Java 1.2 added Java 2D, which expanded the print capabilities to support greater control over multiple page printing and other features. (We should point out that printing only works with applications since the SecurityManager in browser JVMs blocks printing from applets.)

In Java graphics the usual job of the paint() method in AWT and the paintComponent() method in Swing is to send drawing commands to the monitor screen. Java printing simply entails sending drawing commands to the printer instead of the monitor screen. In rendering Java components, we have seen that a Graphics context object is passed to the paint() and paintComponent() methods. To render to the printer, you obtain an instance of PrintGraphics, which is a subclass of Graphics, and pass it to the paint() or paintComponent() method.

Introduction

Chapter 16 introduced distributed computing, the UML notation language, and the design of the server side of a client/server application. Chapter 17 described the client side. Before beginning an actual implementation, it was necessary to describe Java RMI in Chapter 18. Then we took a brief detour in Chapter 19 to describe CORBA as an alternative to RMI. Now that we have all the pieces, we can put them together to build a simple example of a distributed computing application in which the calculation engine is implemented completely in Java. If the calculation engine involves legacy code in a language other than Java, then we must use JNI (the Java Native Interface, which is described in Chapter 22).

The sample application

A real client/server application using the design of Chapters 16 and 17 will be more complex than the sample described here. In fact, if the application were not somewhat complex, there would be little reason to implement it in a client/server design in the first place! However, for the sake of demonstration purposes and to provide a template for the reader's own applications, we provide a simple application that illustrates the important features of the client/server design presented in Chapters 16 and 17.

Recall that the client/server system designed earlier assumed a time-dependent simulation – i.e. one with a solution that varies as a function of time. The same approach could also work with monitoring and controlling a real system such as a remote sensor.

Introduction

Chapter 20 developed a complete client/server application in which both the client code and the server-side code were implemented completely in Java. Pure Java on the client side is desirable for many reasons – platform portability, rich user interface, object-oriented programming environment, ability to run as an application, an applet or a Java Web Start application, etc. For many of the same reasons, a pure Java server offers obvious advantages too. However, for some calculation-intensive processing tasks, particularly if legacy code in another language already exists, it can be advantageous for a Java program to gain access to code written in another language such as C or Fortran.

Java permits calls to code written in languages other than Java. Such external languages are referred to as “native” languages, and the API for accessing them is called the Java Native Interface, or JNI [1]. The decision to use JNI should be made with great care. JNI is designed for use when it is necessary to take advantage of platform-specific functionality that is not available within the Java Virtual Machine. There are two key concepts in that previous sentence – necessary and platform-specific functionality. To utilize platform-specific functionality via JNI obviously removes Java's platform portability. In fact, any use of JNI at all renders a Java application no longer platform portable since the Java application requires a native shared object library for each platform to which it is targeted.

Introduction

Java provides a consistent framework for all input/output. That framework centers on the concept of a stream. A stream in Java is a sequential flow of bytes in one direction. There is an output stream that carries text to the console and a corresponding input stream that brings text from the keyboard. Another type of output stream carries data to a file, and a corresponding input stream brings data into a program from a file. There is another output stream that sends data through a network port to another computer on the network while an input stream brings in data through a network port from such a source.

The bulk of Java I/O classes belong to the java.io package. (See pediagram in Figure 9.1.) The class hierarchy builds on the base classes InputStream, OutputStream, Reader, and Writer to provide a wide range of input and output tasks. In addition, this package holds stream classes that wrap a stream to add more capabilities to it. Some I/O classes provide a destination or source, such as a file or an array. Others process the stream in some way such as buffering or filtering the data.

Packages involving I/O include:

• java.io – the primary Java I/O classes

• java.nio, java.nio.* – a set of five packages new with Java 1.4 based on the concept of channels that represent an open connection to a hardware device, file, or other entity. Channels don't supplant streams but rather work with them to add additional capabilities and enhanced scaling when working with large numbers of connections

• […]

Introduction

In Chapter 14 we showed how to build a basic web server that sends files to browsers or to browser-like clients. In this chapter we present a more interesting socket-based client/server demonstration system that goes beyond just transmission of web pages. This new server sends data to a client, which then displays the data in histograms. This type of client/server system could be quite useful in various applications such as transmitting data from a remote experiment, running diagnostics under the direction of a client, installing calibration settings, and controlling an instrument remotely. For demonstration purposes, our server generates simulated data.

As in Chapter 14 we use sockets for our client/server communications [1–3]. Later chapters present RMI and CORBA based approaches. In a step-by-step manner we describe the concepts and the code techniques used in the client and server demonstration programs.

The client/server design

For the web server discussed in Chapter 14 we used socket communications. The server monitors a port with a ServerSocket, which returns a socket for a client whenever one requests a connection. The socket is passed to a thread that receives a request from the client for a file and then transmits that file if it is available. The server then breaks the connection and the session ends.

We can, however, create a client/server system in which the server maintains a connection for as long as the client desires.

Introduction

Over the last few years, a new distributed computing technology based on the now-ubiquitous World Wide Web and known as web services has become very popular. In this chapter we introduce web services and briefly discuss how the technology can be used in a scientific application. We also introduce the closely-related Extensible Markup Language (XML). These are both large subjects. A full treatment is outside the scope of this book, but this chapter is designed to give the interested reader enough basic information to get started and pointers on where to look for more.

Introducing web services for distributed computing

We have already learned about distributed computing in the abstract sense using UML in Chapters 16 and 17. And we've learned concrete implementations using Java RMI in Chapters 18 and 20 and CORBA in Chapter 19. Both RMI and CORBA are technologies invented to implement distributed computing. One can think of both as transport mechanisms used to move data and, at least in the case of RMI, objects from clients to servers and back. There are other technologies for distributed computing as well, such as the low-level socket based networking technologies discussed in Chapters 14 and 15, and higher-level proprietary single-platform technologies, particularly Microsoft® products, that are not of interest to this book. Web services offer another alternative technology for distributed computing.

Introduction

Chapter 16 introduced distributed computing and enough UML to describe server-side interactions. In this chapter we describe the design of the client for a distributed scientific application in which the computationally intense calculations are performed on a remote server. Like the server, the client details necessarily depend heavily on the calculation being performed and the data that is to be presented to the user. Nevertheless we can provide some general guidelines that should apply to many scientific applications.

Multithreaded client

Recall that the server in Chapter 16 is running on a remote machine, at least conceptually, and is generating results continuously as the simulation is running. To avoid problems with intervening firewalls, we designed the server to be polled by the client rather than using a callback from the server to the client when new data is available. That is, the client must poll the server periodically to retrieve the results being calculated by the server. Assuming that the server calculation is generating results somewhat uniformly, we clearly would prefer for the client to poll the server on a regular basis. Meanwhile, once the client receives the current set of results, the client must display them to the user in some fashion and allow the user to interact with the displayed data. Whenever human users are involved, one can be assured that the user's actions will not be uniform and regular.