Зарубежная периодика по тематике ИПИ РАН, выпуск № 4, сентябрь 2006 г

Зарубежная периодика по тематике ИПИ РАН

Выпуск № 4, сентябрь 2006 г.

Материалы подготовлены лаб. 13

IEEE Transactions on Parallel & Distributed Systems, Jan2005, Vol. 16 Issue 1,

ISSN:

Publisher Information: IEEE 445 Hoes Lane Piscataway, New Jersey United States of America http://www. ieee. org/portal/site

Труды Института Инженеров по Электротехнике и Электронике (США)

«Параллельные и распределенные системы»

Том 16, вып. 1 (Январь 2005 г.)

СТАТЬИ

1. Редакционная статья.

Editor's : Pen-Chung Yew. p1-3, 3p; (AN )

2. Обнаружение децентрализованной сходимости алгоритма для асинхронных параллельных итеративных алгоритмов.

A Decentralized Convergence Detection Algorithm for Asynchronous Parallel Iterative Algorithms.

By: Bahi, Jacques M.; Contassot-Vivier, Sylvain; Couturier, Raphael; Vernier, Flavien. P 4-13, 10p;

Ключевые слова: *ALGORITHM, *ASYNCHRONOUS transfer mod, *BROADBAND communication system, *CONVERGENC, *ITERATIVE methods (Mathematics, *NUMERICAL analysis

Author-Supplied Keywords: asynchronis, convergence detection, Parallel iterative algorithms

Abstract: We introduce a theoretical algorithm and its practical version to perform a decentralized detection of the global convergence of parallel asynchronous iterative algorithms. We prove that, even if the algorithm is completely decentralized, , the detection of global convergence is achieved on one processor under the classical conditions. The proposed algorithm is very useful in the context of grid computing in which the processors are distributed and in which detecting the convergence, on a master processor may be penalizing or even impossible as in Peer to Peer computation frameworks. Finally, the efficiency of the practical algorithm is illustrated in a typical experiment. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Laboratoire d'Informatique de l'Universite de Franche-Comte, FRE CNRS 2661, IUT de Belfort-Montbeliard, , BP 527, 90016 Belfort, France.

3. Подход, основанный на распределении процессов для мультисенсорных систем совместной обработки разнородных данных и географическом разделении пространства данных.

A Process Distribution Approach for Multisensor Data Fusion Systems Based on Geographical Dataspace : Storms, Patrick P. A.; Van Veelen, J. Bernard; Boasson, Erik. p14-23, 10p;

Ключевые слова: COMBINATORIAL analysis, CORRELATION (Statistics), DETECTORS, SIGNAL processing, SYSTEM design, TESSELLATIONS (Mathematics)

Author-Supplied Keywords: data model, sensor fusion, command and control, Distributed architectures

Abstract: In this work, we present a new approach to distributed sensor data fusion (SDF) systems in multitarget tracking, called TSDF (Tessellated SDF), centered around a geographical partitioning (tessellation) of the data. A functional decomposition divides SDF into components that can be assigned to processing units, parallelizing the processing. The tessellation implicitly defines the set of tracks potentially yielding correlations with the sensor plots (observations) in a tile. Some tracks may occur as correlation candidates for multiple tiles. Conflicts caused by correlations of such tracks with plots in different tiles, are resolved by combining all involved tracks and plots into independent data association problems. The benefit of the TSDF approach to a clustering-based process distribution is independence of the problem space, which yields better scalability and manageability characteristics. The TSDF approach allows scaling in more than one way. It allows SDF for single sensor, multiple sensors on a single platform, and even for multiple sensors on multiple platforms. It also provides the flexibility to scale the processing to the size of the problem. This enables a better control of the throughput, to meet various timing constraints. [ABSTRACT FROM AUTHOR]

4. Параллельное использование алгоритма обратного распространения в сетях рабочих станций.

Parallel Implementation of Back-Propagation Algorithm in Networks of : Suresh, S.; Omkar, S. N.; Mani, , V.. p24-34, 11p;

Ключевые слова: MEMORY, OPTICAL character recognition devices, OPTICAL scanners, PERCEPTION, TELECOMMUNICATION systems

Author-Supplied Keywords: back-propagation

network of workstation, optical character recognition, performance measure, divisible load theory, Multilayer perceptron

Abstract: This paper presents an efficient mapping scheme for the multilayer perceptron (MLP) network trained using back-propagation (BP) algorithm on network of workstations (NOWs). Hybrid partitioning (HP) scheme is used to partition the network and each partition is mapped on to processors in NOWs. We derive the processing time and memory space required to implement the parallel BP algorithm in NOWs. The performance parameters like speed-up and space reduction factor are evaluated for the HP scheme and it is compared with earlier work involving vertical partitioning (VP) scheme for mapping the MLP on NOWs. The performance of the HP scheme is evaluated by solving optical character recognition (OCR) problem in a network of ALPHA machines. The analytical and experimental performance shows that the proposed parallel algorithm has better speed-up, less communication time, and better space reduction factor than the earlier algorithm. This paper also presents a simple and efficient static mapping scheme on heterogeneous system. Using divisible load scheduling theory, a closed-form, expression for number of neurons assigned to each processor in the NOW is obtained. Analytical and experimental results for, static mapping problem on NOWs are also presented. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Aerospace Engineering, Indian Institute of Science, Bangalore- India.

5. Хранилище данных с прикрепленным виртуальным интерфейсом

VI-Attached Database : Zhou, Yuanyuan; Bilas, Angelos; Jagannathan, Suresh; Xinidis, Dimitrios; Dubnicki, Cezary; Li, Kai. p35-50, 16p;

Ключевые слова: *DATABASE design, DATABASES, INFORMATION retrieval, PROTOTYPES, Engineering

Author-Supplied Keywords: storage serve, Virtual Interlace, user-level communication, , performance evaluation, server cluster, Database storage

Abstract: This article presents a VI-attached database storage architecture to improve database transaction rates. More specifically, we examine how VI-based interconnects can be used to improve I/O path performance between a database server and a storage subsystem. To facilitate the interaction between client applications and a VI-aware storage system, we design and implement a software layer called DSA, that is layered between applications and VI. DSA takes advantage of specific VI features and deals with many of its shortcomings. We provide and evaluate one kernel-level and two user-level implementations of DSA. These implementations trade transparency and generality for performance at different degrees and, unlike research prototypes, are designed to be suitable for real-world deployment. We have also investigated many design trade offs in the storage cluster. We present detailed measurements using a commercial database management system with both microbenchmarks and industrial database workloads on a mid-size, 4 CPU, and a large, 32 CPU, database server. We also compare the effectiveness of Vl-attached storage with an iSCSI configuration, and conclude that storage protocols implemented using DSA over VI have significant performance advantages. More generally, our results show that VI-based interconnects and user-level communication can improve all aspects of the I/O path between the database system and the storage back-end. We also find that to make effective use of VI in I/O intensive environments, we need to provide substantial additional functionality than what is currently provided by VI. Finally, new storage APIs that help minimize kernel involvement in the I/O path are needed to fully exploit the benefits of VI-based communication. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801.

2ICS-FORTH, STEP-C, PO Box 1385, Heraklion, GR-71110, Greece, 3Department of Computer Science, Purdue University, West Lafayette, IN 47907, 4NEC Labs, 4 Independence Way, Princeton, NJ 08540.

5 Department of Computer Science, Princeton University, Princeton, NJ 08540.

6. Метод проектирования оптической коммуникационной сети с разделением по длине волны, оптимизированный по соотношению «стоимость-эффективность».

Cost-Effective Designs of WDM Optical : Yang, Yuanyuan; Wang, Jianchao. p51-66, 16p;

Ключевые слова: MATHEMATICAL models, MULTIPLEXING, OPTICAL communications, COMPUTER systems, WAVELENGTH division multiplexing

Author-Supplied Keywords: optical interconnect, optical switches, network architecture, sparse crossbar, wavelength conversion, permutation, multicast, multistage networks, Wavelength-division-multiplexing (WDM)

Abstract: Optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has become a promising networking choice to meet ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/communication applications, such as data browsing in the World Wide Web, multimedia conferencing, e-commerce, and video-on-demand services. As optics becomes a major networking media in all communications needs, optical interconnects will inevitably play an important role in interconnecting processors in parallel and distributed computing systems. In this paper, we consider cost-effective designs of WDM optical interconnects for current and future generation parallel and distributed computing and communication systems. We first categorize WDM optical interconnects into two different connection models based on their target applications: the wavelength-based model and the fiber-link-based model. Most of existing WDM optical interconnects belong to the first category. We then present a minimum cost design for WDM optical interconnects under wavelength-based model by using sparse crossbar switches instead of full crossbar switches in combination with wavelength converters. For applications that use the fiber-link-based model, we show that network cost can be significantly reduced, and present such a minimum cost design for WDM optical interconnects under this model. Finally, we generalize the idea used in the design for the fiber-link-based model to WDM optical interconnects under the wavelength-based model, and obtain another new design that can trade off switch cost with wavelength converter cost in this type of WDM optical interconnect. The results in this paper are applicable to any emerging optical switching technologies, such as SOA-based and MEMS-based technologies. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Electrical and Computer Engineering, State University of New York, Stony Brook, NY, , 2East Isle Technologies, Inc., Setauket, NY 11733.

7. Двухуровневая программная архитектура для микропроцессоров cc-NUMA с сильно варьируемой размерностью памяти.

A Two-Level Directory Architecture for Highly Scalable cc-NUMA : Acacio, Manuel E.; Gonzalez, Jose Garcia, Jose M.; Duato, Jose. p67-79, 13p;

Ключевые слова: COMPUTER simulation, ELECTRONIC digital computers, INFORMATION technology, MEMORY, MULTIPROCESSORS, SIMULATION methods

Author-Supplied Keywords: directory memory overhead, two-level directory architecture, compressed sharing codes, unnecessary coherence messages, cc-NUMA multiprocessor.

Abstract: One important issue the designer of a scalable shared-memory multiprocessor must deal with is the amount of extra memory required to store the directory information. It is desirable that the directory memory overhead be kept as low as possible, and that it scales very slowly with the size of the machine. Unfortunately, current directory architectures provide scalability at the expense of performance. This work presents a scalable directory architecture that significantly reduces the size of the directory for large-scale configurations of a multiprocessor without degrading performance. First, we propose multilayer clustering as an effective approach to reduce the width of directory entries. Based on this concept, we derive three new compressed sharing codes, some of them with a space complexity of O(log₂(log₂(N))) for an N-node system. Then, we present a novel two-level directory architecture to eliminate the penalty caused by compressed directories in general. The proposed organization consists of a small full-map first-level directory (which provides precise information for the most recently referenced lines) and a compressed second-level directory (which provides in-excess information for all the lines). The proposals are evaluated based on extensive execution-driven simulations (using RSIM) of a 64-node cc-NUMA multiprocessor. Results demonstrate that a system with a two-level directory architecture achieves the same performance as a multiprocessor with a big and nonscalable full-map directory, with a very significant reduction of the memory overhead. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1 Departamento de Ingeniería y Tecnología de Computadores, Universidad de Murcia, Campus de Espinardo

S/N, Facultad de Informática, 30071 Murcia, Spain, 2 Intel Barcelona Research Center, Intel Labs Barcelona, C/Jordi Girona 29, Edif. Nexus 2, Planta 3, 08034 Barcelona, Spain, 3Departamento de Informática de Sistemas y Computadores, Universidad Politécnica de Valencia, Camino de Vera S/N, 46010 , Valencia, Spain.

8. Параллельный процессор UCSC Kestrel

The UCSC Kestrel Parallel : Di Blas, Andrea; Dahle, David M.; Diekhans, Mark; Grate, Leslie; Hirschberg, Jeffrey; Karplus, Kevin; Keller, Hansjorg; Kendrick, Mark; Mesa-Martinez, Francisco J.; Pease, David; Rice, Eric; Schultz, Angela; Speck, Don; Hughey, Richard. p80-92, 13p;

Ключевые слова: ALGORITHMS, AMINO acid sequence, ARTIFICIAL intelligence, DNA, PARALLEL processing (Electronic computers, UNIVERSITY of California (Santa Cruz, Calif.)

Author-Supplied Keywords: systolic array, biological sequence analysis, DNA, computational chemistry, image processing, VLSI system design, computer architecture, high performance computing, Parallel processing

Abstract: The architectural landscape of high-performance computing stretches from superscalar uniprocessor to explicitly parallel systems to dedicated hardware implementations of algorithms. Single-purpose hardware can achieve the highest performance and uniprocessors can be the most programmable. Between these extremes, programmable and reconfigurable architectures provide a wide range of choice in flexibility, programmability, computational density, and performance. The UCSC Kestrel parallel processor strives to attain single-purpose performance while maintaining user programmability. Kestrel is a single-instruction stream, multiple - data stream (SIMD) parallel processor with a 512-element linear array of 8-bit processing elements. The system design focuses on efficient high-throughput DNA and protein sequence analysis, but its programmability enables high performance on computational chemistry, image processing, machine learning, and other applications. The Kestrel system has had unexpected longevity in its utility due to a careful design and analysis process. Experience with the system leads to the conclusion that programmable SIMD architectures can excel in both programmability and performance. This paper presents the architecture, implementation, applications, and observations of the Kestrel project at the University of California at Santa Cruz. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Computer Engineering, University of California, Santa Cruz, 1156 High Street, Santa Cruz, CA 95064, 2 Intel Corporation, 3Center for Biomolecular Science and Engineering, Baskin Engineering, University of California, Santa Cruz, 1156 High Street, Santa Cruz, CA 95064, 4 Intel Corporation, DP2-400, 2800 Center Drive, DuPont, WA , 5 Berne University of Applied Sciences, Switzerland., 6 IBM Almaden Research Center, 650 Harry, Road, San Jose, CA 95044.

IEEE Transactions on Parallel & Distributed Systems, Jan2005, Vol. 16 Issue 4,

ISSN:

Publisher Information: IEEE 445 Hoes Lane Piscataway, New Jersey United States of America http://www. ieee. org/portal/site

Труды Института Инженеров по Электротехнике и Электронике (США)

«Параллельные и распределенные системы»

Том 16, вып. 4 (Январь 2005 г.)

СТАТЬИ

1. Динамический баланс загрузки и оценки эффективной загрузки асинхронных итеративных алгоритмов.

Dynamic Load Balancing and Efficient Load Estimators for Asynchronous Iterative : Bahi, Jacques M.; Contassot-Vivier, Sylvain; Couturier, Raphael. p289-299, 11p;

Ключевые слова: *ALGORITHMS, ASYNCHRONOUS circuits, CALCULUS, DIFFERENTIAL equations, DIFFERENTIAL equations, Partial, DIGITAL electronics

Abstract: In a previous paper [1], we have shown the very high power of asynchronism for parallel iterative algorithms in a global context of grid computing. In this article, we study the interest of coupling load balancing with asynchronism in such algorithms. After proposing a noncentralized version of dynamic load balancing which is best suited to asynchronism, we verify its efficiency by some experiments on a general Partial Differential Equation (PDE) problem. Finally, we give some general conditions for the use of load balancing to obtain good results with this kind of algorithm and discuss the choice of the residual as an efficient load estimator. [ABSTRACT FROM AUTHOR]

2. Конвейерная широковещательная рассылка сообщений на гетерогенной платформе.

Pipelining Broadcasts on Heterogeneous : Beaumont, Olivier; Legrand, Arnaud; Marchal, Loris; Robert, Yves, p300-313, 14p;

Ключевые слова: ALGORITHMS, BROADCASTING, DYNAMIC programming, ELECTRONIC data processing -- Distributed processing, COMPUTER programming, COMPUTATIONAL grids (Computer systems)

Abstract: In this paper, we consider the communications involved by the execution of a complex application, deployed on a heterogeneous platform. Such applications extensively use macrocommunication schemes, for example, to broadcast data items. Rather than aiming at minimizing the execution time of a single broadcast, we focus on the steady-state operation. We assume that there is a large number of messages to be broadcast in pipeline fashion, and we aim at maximizing the throughput, i. e., the (rational) number of messages which can be broadcast every time-step. We target heterogeneous platforms, modeled by a graph where resources have different communication and computation speeds. Achieving the best throughput may well require that the target platform is used in totality: We show that neither spanning trees nor DAGs are as powerful as, general graphs. We show how, to compute the best throughput using linear programming, and how to exhibit a periodic schedule, first when restricting to a DAG, and then when using a general graph. The polynomial compactness of the description comes from the decomposition of the schedule into several broadcast trees that are used concurrently to reach the best throughput. It is important to point out that a concrete scheduling algorithm based upon the steady-state operation is asymptotically optimal, in the class of all possible schedules (not only periodic solutions). [ABSTRACT FROM AUTHOR]

3. Диагностируемость регулярных сетей

Diagnosabilities of Regular : Guey-Yun Chang; Chang, Gerard J.; Gen-Huey Chen, p314-323, 10p;

Ключевые слова: ELECTRONIC digital computers, ELECTRONIC systems, MULTIPROCESSORS, RELIABILITY (Engineering), FAULT tolerance (Engineering), COMPUTER systems

Abstract: In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. [28] and the pessimistic diagnosis strategy proposed by Friedman [18]. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Computer Science and Engineering, National Taiwan University, Taipei 10617, Taiwan, 2Department of Mathematics, National Taiwan University, Taipei 10617, Taiwan; Mathematics Division, National Center for Theoretical Sciences at Taipei.

4. Оптимизация полосы пропускания трафика Интернет для серверов в режиме обобщенного разделения времени работы процессоров.

Bandwidth Optimization for Internet Traffic In Generalized Processor Sharing : Ju Yong Lee; Sunggon Kim, Deokseong Kim; Dan Keun Sung. p324-334, 11p;

Ключевые слова: BROADBAND communication systems, MATHEMATICAL optimization, SIMULATION methods, BANDWIDTHS, WEB servers, PROGRAM transformation (Computer programming)

Abstract: Bandwidth optimization is considered when several classes of Internet traffic are served in Generalized Processor Sharing (GPS) servers. Internet traffic shows self-similar patterns that make it difficult to obtain analytical performance in GPS. Thus, for performance estimation of different classes of traffic, we use fluid simulation techniques that can reduce the simulation complexity, compared to packet-level simulation. Using the relationship between the guaranteed bandwidth vector and the corresponding performance, we propose a bandwidth optimization problem to minimize the total bandwidth such that performance requirements are satisfied. We use an exterior penalty function method to solve the optimization problem. However, a penalized objective function may have local minimum which is not a global minimum. Thus, we propose a new methodology to circumvent the limitation of the exterior penalty function method. [ABSTRACT FROM AUTHOR]

5. Алгоритмы маршрутизации сети с шинной структурой, соединенной по методу гиперкуба.

Routing Algorithms on the Bus-Based Hypercube : Lee-Juan Fan; Chang-Biau Yang; Shyue-Horng Shiau, p335-348, 14p;

Ключевые слова: ALGORITHMS, HYPERCUBE networks (Computer networks), MICROCOMPUTERS -- Buses, COMPUTER programming, HIGH performance processor, ROUTING-machines

Abstract: In this paper, we study the properties of the bus-based hypercube, denoted as U(n, b), which is a kind of multiple-bus networks (MBN). U(n, b) consists of 2^TL processors and 2^b buses, where 0 ≤ b ≤ n - 1, and each processor is connected to either [b+2/2] or [b+1/2] buses. We show that the diameter of U(n, b) is [b+1/2] if b ≥ 2. We also present an algorithm to select the best neighbor processor via which we can obtain one shortest routing path. In U(n, b), we show that if there exist some faults, the fault diameter DF(n, b, f) ≤ b + 1, where f is the sum of bus faults and processor faults and 0 ≤ f ≤ [b-3/2]. Furthermore, we also show that the bus - fault diameter DB(n, b, f) ≤ [b/2] +3, where 0 &les' [b-1/2] and f is the number of bus faults. These results improve significantly the previous result that DB(n, b, f) ≤ b + 2f + 1, where f is the number of bus faults. [ABSTRACT FROM AUTHOR]

6. Эффективный, с учетом близости, баланс нагрузки для систем класса P2P, использующих распределенную хэш-таблицу(DHT).

Efficient, Proximity-Aware Load Balancing for DHT-Based P2P : Yingwu Zhu; Yiming Hu, p349-361, 13p;

Ключевые слова: BALANCING of machinery, COMPUTER network architectures, PERMUTATIONS, COMPUTER programming, HIGH performance processors, WEB servers

Abstract: Many solutions have been proposed to tackle the load balancing issue in DHT-based P2P systems. However, all these solutions either ignore the heterogeneity nature of the system, or reassign loads among nodes without considering proximity relationships, or both. In this paper, we present an efficient, proximity-aware load balancing scheme by using the concept of virtual servers. To the best of our knowledge, this is the first work to use proximity information in load balancing. In particular, our main contributions are: 1) Relying on a self-organized, fully distributed κ-ary tree structure constructed on top of a DHT, load balance is achieved by aligning those two skews in load distribution and node capacity inherent in P2P systems-that is, have higher capacity nodes carry more loads; 2) proximity information is used to guide virtual server reassignments such that virtual servers are reassigned and transferred between physically close heavily loaded nodes and lightly loaded nodes, thereby minimizing the load movement cost and allowing load balancing to perform efficiently; and 3) our simulations show that our proximity-aware load balancing scheme reduces the load movement cost by 11-65 percent for all the combinations of two representative network topologies, two node capacity profiles, and two load distributions of virtual servers. Moreover, we achieve virtual server reassignments in O(log N) time. [ABSTRACT FROM AUTHOR]

7. Повышение надежности маршрутизации источника с мобильных сетях, использующих игровой сценарий.

Improving Source Routing Reliability in Mobile Ad Hoc : Song Guo; Oliver Yang; Yantal Shu, p362-373, 12p;

Ключевые слова: COMPUTER networks, INFORMATION networks, MOBILE communication systems, RELIABILITY (Engineering), ROUTERS (Computer networks), INTERNETWORKING devices, BACK up systems

Abstract: In this paper, we propose a novel on-demand routing protocol called Backup Source Routing (BSR) to establish and maintain backup routes that can be utilized after the primary path breaks. The key advantage of BSR is the reduction of the frequency of route discovery flooding, which is recognized as a major overhead in on-demand protocols. We define a new routing metric, called the route reliability, and use it to provide the basis for the backup path selection. We use a heuristic cost function to develop an analytical model and an approximation method to measure this metric. Various algorithms for our BSR protocol in the route discovery phase and route maintenance phase have been designed based on this cost function. Extensive simulations demonstrated that our routing strategy has two interesting features: 1) In less stressful situations of lower mobility, BSR has similar performance to DSR. 2) In more challenging situations of high mobility, BSR can improve the performance significantly. [ABSTRACT FROM AUTHOR]

8. Размещение совместно используемых данных в мобильной вычислительной системе: использование локальной и глобальной оптимизации.

Shared Data Allocation in a Mobile Computing System: Exploring Local and Global : Wen-Chih Peng; Ming-Syan Chen, p374-384, 11p;

Find More Like ThisShared Data Allocation in. a Mobile Computing System: Exploring Local and Global Optimization.

Authors: Wen-Chih Peng1 *****@***nctu. edu. tw

Ming-Syan Chen1 *****@***ee. ntu. edu. tw

Ключевые слова: ALGORITHMS, ELECTRONIC data processing, INFORMATION networks, MOBILE communication systems, MOBILE computing, COMPUTER systems

Abstract: In this paper, we devise data allocation algorithms that can utilize the knowledge of user moving patterns for proper allocation of shared data in a mobile computing employing the data allocation algorithms devised, the occurrences of costly remote accesses can be minimized and the performance of a mobile computing system is thus improved. The data allocation: algorithms for shared data, which are able to achieve local optimization and global optimization, are developed. Local optimization refers to the optimization that the likelihood of local data access by an individual mobile user is maximized whereas global optimization refers to the optimization that the likelihood of local data access by all mobile users is maximized. Specifically, by exploring the features of local optimization and global optimization, we devise algorithm SD-local and algorithm SD-global to achieve local optimization and global optimization, respectively. In general, the mobile users are divided into two types, namely, frequently moving users and infrequently moving users. A measurement, called closeness measure which corresponds to the amount of the intersection between the set of frequently moving user patterns and that of infrequently moving user patterns, is derived to assess the quality of solutions provided by SD-local and SD-global. Performance of these data allocation algorithms is comparatively analyzed. From the analysis of SD-local and SD-global, it is shown that SD-local favors infrequently moving users whereas SD-global is good for frequently moving users. The simulation results show that the knowledge obtained from the user moving patterns is very important in devising effective data allocation algorithms which can lead to prominent performance improvement in a mobile computing system. [ABSTRACT FROM AUTHOR]

Data & Knowledge Engineering, Feb2005, Vol. 52 Issue 2,

ISSN: X

Publisher Information: Elsevier Science Publishers B. V.

PO Box 211 Amsterdam 1000 AE Netherlands

Журнал «Инженерия данных и знаний», том. 52, вып. 2, 2005 год

СТАТЬИ

1. XML схема и управление даннымии. Редакционная статья.

XML schema and data management, p181-183, 3p;

Editorial

2. Объектная структура для управления параллельной разметкой XML.

A framework for management of concurrent XML : Dekhtyar, Alex; Iacob, p185-208, 24p;

Ключевые слова: DOCUMENT markup languages, SYMBOLISM, XML (Document markup language), ENCODING

Author-Supplied Keywords: XM, Concurrent markup

Abstract: The problem of concurrent markup hierarchies in XML encodings of documents has attracted attention of a number of humanities researchers in recent years. The key problem with using concurrent hierarchies to encode documents is that markup in one hierarchy is not necessarily well-formed with respect to the markup in another hierarchy. Previously proposed solutions to this problem rely on the XML expertise of the editors and their ability to maintain correct DTDs for complex markup languages. In this paper, we approach the problem of maintenance of concurrent XML markup from the Computer Science perspective. We propose a framework that allows the editors to concentrate on the semantic aspects of the encoding, while leaving the burden of maintaining XML documents to the software. The paper describes the formal notion of the concurrent markup languages and the algorithms for automatic maintenance of XML documents with concurrent markup. [ABSTRACT FROM AUTHOR; Copyright 2005 Elsevier]

Author Affiliations: 1Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA

3. CX-DIFF: a change detection algorithm for XML content and change visualization for : Jacob, Jyoti; Sachde, Alpa; Chakravarthy, Sharma. p209-230, 22p;

Ключевые слова: VISUAL perception, VISUAL programming languages (Computer science), WORLD Wide Web, XML (Document markup language)

Author-Supplied Keywords: World Wide Web, Notification, XML, Change detection

Abstract: The World Wide Web is an omni-present and ever-expanding source of data. The exponential increase of information on the web has affected the manner in which it is accessed, disseminated and delivered. The emphasis has shifted from mere viewing of information to efficient retrieval and monitoring of selective changes to information content. Hence, an effective monitoring system for change detection and notification based on user-profile is needed. WebVigiL is a general-purpose, active capability-based information monitoring and notification system for HTML and XML documents. It handles specification, management, and propagation of customized changes as requested by a user. A novel aspect of WebVigiL is its ability to detect customized changes on the content of the document. This paper deals with change detection to XML documents, and change visualization in WebVigiL. The ordered tree property of an XML document is exploited for change detection. In this paper, we propose an algorithm to handle customized change detection to the contents of XML documents based on user-intent. In addition, an optimization to this algorithm is presented that has a better performance with certain desired characteristics. We also discuss various change visualization schemes to display the changes computed by WebVigiL. We highlight the change presentation in WebVigiL and briefly describe the rest of the system. [ABSTRACT FROM AUTHOR; Copyright,2005 Elsevier]

4. О непротиворечивости шаблонов документов языка XML.

On the consistency of XML : Lu, Shiyong; Sun, Yezhou; Atay, Mustafa; Fotouhi, Farshad, p231-247, 17p;

Ключевые слова: ALGEBRA, ALGORITHMS, DOCUMENT markup languages, XML (Document markup language)

Author-Supplied Keywords: DTD

XML, Consistency, Algorithm

Abstract: DTD has been widely used as the schema language for XML documents. A DTD describes the structure of a collection of similar XML documents. The consistency problem of XML DTDs concerns the question that given a DTD <f>D</f>, if there exists any finite XML document that conforms to <f>D</f>. This issue is important because one wants to know whether a DTD specification is meaningful. In this paper, we formalize the notion of the consistency of DTDs, identify a sufficient and necessary condition for a DTD to be consistent, and propose a linear algorithm, DTDCon, for the consistency checking problem.[ABSTRACT FROM AUTHOR; Copyright 2005 Elsevier]

Author Affiliations: 1Department of Computer Science, Wayne State University, 430 State Hall, 5143 Cass Avenue, Detroit, ,MI 48202, USA

5. Bio2X: a rule-based approach for semi-automatic transformation of semi-structured biological data to : Yang, Song; Bhowmick, Sourav S.; Madria, Sanjay, p249-271,

Ключевые слова: COMPUTER files, DOCUMENT markup languages, MACHINE theory, XML (Document markup language, Author-Supplied Keywords: Flat files, Rule base, Machine learning, XML, Transformer

Abstract: Data integration of geographically dispersed, heterogeneous, complex biological databases is a key research area. One of the key features of a successful data integration system is to have a simple self-describing data exchange format. However, many of the biological databases provide data in flat files which are poor data exchange formats. Fortunately, XML can be viewed as a powerful data model and better data exchange format. In this paper, we present the Bio2X system that transforms flat file data into highly hierarchical XML data using rule-based machine learning technique. Bio2X has been fully implemented using Java. Our experiments to transform real world biological data demonstrate the effectiveness of the Bio2X approach. [ABSTRACT FROM AUTHOR; Copyright 2005 Elsevier]

Author Affiliations: 1School of Computer Engineering, Nanyang Technological University, Singapore Singapore, 2Department of Computer Science, University of Missouri-Rolla, Rolla 65409, USA

6. Editorial board. Data & Knowledge Engineering, Feb2005, Vol. 52 Issue 2, pCO2-CO2, 1p;

SIAM Review, 2005, Vol. 47 Issue 1,

Society for Industrial and Applied Mathematics

3600 University City Science Center | Philadelphia, PA 19104 USA

Phone: +800 | FAX: +999

Обзоры Общества промышленной и прикладной математики, том. 47,

вып. 1, 2005 год

Полный текст приводимых ниже обзоров доступен в формате.pdf

1. Аннотации обзоров сборника

SURVEY and : LeVeque, Randy. p1-1, 1p;

Ключевые слова: EIGENVALUES, ITERATIVE methods (Mathematics), MATRICES, RECURRENT sequences (Mathematics)

People: WATKINS, David

Abstract: Focuses on an article by David Watkins concerning eigenvalues. Interpretation of eigenvalues that arises naturally in the context of linear recurrence relations; Application of iterative methods for the eigenvalue problem to cyclic matrices; Eigenvalue problems of special form.

2. Проблемы определения характеристического числа продукции.

Product Eigenvalue : Watkins, David S.. p3-40, 38p, 2 graphs;

Ключевые слова: ALGEBRA, ALGORITHMS, EIGENVALUES, MATRICES, VECTOR analysis

Author-Supplied Keywords: QR algorithm, GR algorithm, generalized eigenvalue problem, SVD, symmetric, skew symmetric, positive definite, totally positive, pseudosymmetric, Hamiltonian symplectic, unitary eigenvalue

Abstract: Many eigenvalue problems are most naturally viewed as product eigenvalue problems. The eigenvalues of a matrix A are wanted, but A is not given explicitly. Instead it is presented as a product of several factors: A = A_k A_k-1 ... A₁. Usually more accurate results are obtained by working with the factors rather than forming A explicitly. For example, if we want eigenvalues/vectors of B^T B, it is better to work directly with B and not compute the product. The intent of this paper is to demonstrate that the product eigenvalue problem is a powerful unifying concept. Diverse examples of eigenvalue problems are discussed and formulated as product eigenvalue problems. For all but a couple of these examples it is shown that the standard algorithms for solving them are instances of a generic GR algorithm applied to a related cyclic matrix. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Mathematics, Washington State University, Pullman, WA

3. Состояния скачущего мяча и квантовый хаос.

Bouncing Ball Modes and Quantum : Burq, Nicolas; Zworski, Maciej. p43-49, 7p, 1 diagram, 2c;

Ключевые слова: CHAOTIC behavior in systems, MATHEMATICS, PHYSICS, QUANTUM theory, STADIUM, Author-Supplied Keywords: billiards, quantum ergodicity, eigenfunctions

Abstract: Quantum ergodicity for classically chaotic systems has been studied extensively both theoretically and experimentally in mathematics and physics. Despite this long tradition we are able to prove a new rigorous result using only elementary calculus. In the case of the famous Bunimovich stadium shown in Figure 1, we prove that the wave functions have to spread to any neighborhood of the wings. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Université Paris Sud, Mathématiques, Bât 425, 91405 Orsay Cedex

2Mathematics Department, University of California, Berkeley, CA 94720

4. О решении методом конечных элементов классической проблемы Неймана.

On the Finite Element Solution of the Pure Neumann : Bochev, Pavel; Lehoucq, R. B.. p50-66, 17p, 2 charts, 3 graphs;

Ключевые слова: APPROXIMATION theory, BOUNDARY value problems, FINITE element method, FUNCTIONS, NEUMANN problem, Author-Supplied Keywords: Neumann problem,, Rayleigh--Ritz minimization, regularization, quadratic programming, finite elements

Abstract: This paper considers the finite element approximation and algebraic solution of the pure Neumann problem. Our goal is to present a concise variational framework for the finite element solution of the Neumann problem that focuses on the interplay between the algebraic and variational problems. While many of the results that stem from our analysis are known by some experts, they are seldom derived in a rigorous fashion and remain part of numerical folklore. As a result, this knowledge is not accessible (or appreciated) by many practitioners--both novices and experts--in one source. Our paper contributes a simple, yet insightful link between the continuous and algebraic variational forms that will prove useful. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Sandia National Laboratories, P. O. Box 5800, MS 1110, Albuquerque, NM

5. Метод двумерного распределения данных при параллельном умножении разреженной матрицы-вектора.

A Two-Dimensional Data Distribution Method for Parallel Sparse Matrix-Vector : Vastenhouw, Brendan; Bisseling, Rob H.. p67-95, 29p, 8 charts, 3 diagrams;

Ключевые слова: COMMUNICATION, DISTRIBUTION (Probability theory), MATRICES, MULTIPLICATION, SPARSE matrices, Author-Supplied Keywords: matrix-vector multiplication, parallel computing, recursive bipartitioning, sparse matrix, matrix partitioning

Abstract: A new method is presented for distributing data in sparse matrix-vector multiplication. The method is two-dimensional, tries to minimize the true communication volume, and also tries to spread the computation and communication work evenly over the processors. The method starts with a recursive bipartitioning of the sparse matrix, each time splitting a rectangular matrix into two parts with a nearly equal number of nonzeros. The communication volume caused by the split is minimized. After the matrix partitioning, the input and output vectors are partitioned with the objective of minimizing the maximum communication volume per processor. Experimental results of our implementation, Mondriaan, for a set of sparse test matrices show a reduction in communication volume compared to one-dimensional methods, and in general a good balance in the communication work. Experimental timings of an actual parallel sparse matrix-vector multiplication on an SGI Origin 3800 computer show that a sufficiently large reduction in communication volume leads to savings in execution time. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Image Sciences Institute, University Medical Center Utrecht, P. O. Box 85500, 3508 GA Utrecht, The Netherlands

2Mathematical Institute, Utrecht University, P. O. Box 80010, 3508 TA Utrecht, The Netherlands

6. SNOPT: Алгоритм последовательного квадратичного программирования (SQP) для решения задач оптимизации большой размерности с ограничениями.

SNOPT: An SQP Algorithm for Large-Scale Constrained : Gill, Philip E.; Murray, Walter; Saunders, Michael A.. p99-131, 33p, 7 charts;

Ключевые слова: ALGORITHMS, LAGRANGIAN functions, MATHEMATICAL optimization, NONLINEAR programming, QUADRATIC programming

Author-Supplied Keywords: nonlinear programming, nonlinear inequality constraints, sequential quadratic programming, quasi-Newton methods, limited-memory methods, large-scale optimization

Abstract: Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom). [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Mathematics, University of California, San Diego, La Jolla, CA , 2Department of Management Science and Engineering, Stanford University, Stanford, CA

7. Аналитический обзор использования методов собственного значения вектора при информационном поиске в Интернет.

A Survey of Eigenvector Methods for Web Information : Langville, Amy N.; Meyer, Carl D.. p135-161, 27p, 7 diagrams;

Ключевые слова: EIGENVECTORS, INFORMATION resources management, INFORMATION retrieval, INFORMATION science, WORLD Wide Web, WEB search engines

Author-Supplied Keywords: Markov chain, information retrieval, HITS, PageRank, SALSA, eigenvector

Abstract: Web information retrieval is significantly more challenging than traditional well-controlled, small document collection information retrieval. One main difference between traditional information retrieval and Web information retrieval is the Web's hyperlink structure. This structure has been exploited by several of today's leading Web search engines, particularly Google and Teoma. In this survey paper, we focus on Web information retrieval methods that use eigenvector computations, presenting the three popular methods of HITS, PageRank, and SALSA. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Mathematics, North Carolina State University, Raleigh, NC

8. Обзор содержания двух новых книг по дифференциальным уравнениям в частных производных.

Featured Review: Two New Books on Partial Differential : Guenther, Ronald B.; Thomann, Enrique A.; O'Malley Jr., Robert E.. p165-168, 3p;

Ключевые слова: DIFFERENTIAL equations, Partial, NONFICTION

Reviews & Products: LECTURES on Partial Differential Equations (Book)

INTRODUCTION to Partial Differential Equations, An (Book)

People: RENARDY, Michael, ROGERS, Robert C, ARNOLD, Vladimir L.

Abstract: Reviews two books on partial differential equations. "An Introduction to Partial Differential Equations," 2nd ed., by Michael Renardy and Robert C. Rogers; "Lectures on Partial Differential Equations," by Vladimir L. Arnold.

Author Affiliations: 1Oregon State University

9. Спиновое стекло*): вызов математикам.

Spin Glasses: A Challenge for : Aldous, David; O'Malley Jr., Robert E.. p168-170, 3p;

BOOKS -- Reviews

Ключевые слова: MATHEMATICIANS, NONFICTION

Reviews & Products: SPIN Glasses: A Challenge for Mathematicians (Book)

*) Спиновое стекло – объект, изучаемый физикой твердого тела, прозрачное, твердое, но лишенное внутренней структуры вещество (прим. Переводчика)

10. Введение в принцип неопределенности: теорема Харди о группах Ли.

An Introduction to the Uncertainty Principle, Hardy's Theorem on Lie : Asmar, Nakhlé; O'Malley Jr., Robert E.. p170-172, 3p;

Ключевые слова: HEISENBERG uncertainty principle, NONFICTION

Reviews & Products: INTRODUCTION to the Uncertainty Principle: Hardy's Theorem on Lie Groups, An (Book)

11. Представление об алгебрах Йордана.

ATaste of Jordan : Bertram, Wolfgang; O'Malley Jr., Robert E.. p172-174, 3p;

BOOKS -- Reviews

Ключевые слова: JORDAN algebras, NONFICTION

Reviews & Products: TASTE of Jordan Algebras, A (Book)

People: MCCRIMMON, Kevin

Abstract: Reviews the book "A Taste of Jordan Algebras," by Kevin McCrimmon.

Author Affiliations: 1Institut Elie Cartan, Université Nancy I

12. Комплексная выпуклость и аналитические функционалы.

Complex Convexity and Analytic : Krantz, Steven G.; O'Malley Jr., Robert E.. p174-176, 3p;

BOOKS -- Reviews

Ключевые слова: FUNCTIONALS, NONFICTION

Reviews & Products: COMPLEX Convexity & Analytic Functionals (Book)

People: ANDERSSON, Mats, PASSARE, Mikael, SIGURDSSON, Ragnar

Abstract: Reviews the book "Complex Convexity and Analytic Functionals," by Mats Andersson, Mikael Passare, and Ragnar Sigurdsson.

Author Affiliations: 1Washington University, St. Louis

13. Теория бифуркаций: введение применительно к уравнениям в частных производных.

Bifurcation Theory: An Introduction with Applications to : Kuznetsov, Yu A.; O'Malley Jr., Robert E.. p176-178, 3p;

Ключевые слова: BIFURCATION theory

Reviews & Products: BIFURCATION Theory: An Introduction With Applications to PDEs (Book)

People: KIELHOFER, Hansjorg

Abstract: Reviews the book "Bifurcation Theory: An Introduction With Applications to PDEs," by Hansjorg Kielhöfer.

Author Affiliations: 1Utrecht University

14. Все и даже более: краткая история ∞.

Everything and More: A Compact History of ∞. By: Luke, Russell; O'Malley Jr., Robert E.. p178-182, 5p;

BOOKS -- Reviews

Ключевые слова: INFINITE, NONFICTIO, WALLACE, David Foster

Reviews & Products: EVERYTHING & More: A Compact History of... (Book)

Abstract: Reviews the book "Everything and More: A Compact History of ∞," by David Foster Wallace.

Author Affiliations: 1University of Delaware

15. Криптографические приложения аналитической теории чисел: нижние границы оценки сложности и псевдослучайность.

Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and : Moree, Pieter; O'Malley Jr., Robert E.. p182-185, 4p;

BOOKS -- Reviews

Ключевые слова: NUMBER theory, NONFICTION

Reviews & Products: CRYPTOGRAPHIC Applications of Analytic Number Theory: Complexity Lower Bounds & Pseudorandomness (Book)

People: SHPARLINSKI, Igor

Abstract: Reviews the book "Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness," by Igor Shparlinski.

Author Affiliations: 1Max-Planck-Institut für Mathematik Bonn

16. Теория дифференциальных уравнений: классическая и качественная.

The Theory of Differential Equations: Classical and : O'Malley Jr., Robert E.. p185-186, 2p;

Ключевые слова: *DIFFERENTIAL equations, NONFICTION

Reviews & Products: THEORY of Differential Equations: Classical & Qualitative, The (Book)

People: PETERSON, Allan

KELLEY, Walter

Abstract: Reviews the book "The Theory of Differential Equations: Classical and Qualitative," by Walter Kelley and Allan Peterson.

Author Affiliations: 1University of Washington

17. Панорамное представление геометрии Римана.

A Panoramic View of Riemannian : Osserman, Robert; O'Malley Jr., Robert E.. p186-188, 3p;

Ключевые слова: GEOMETRY, Riemannian, NONFICTION

Reviews & Products: PANORAMIC View of Riemannian Geometry, A (Book)

People: BERGER, Marcel

Abstract: Reviews the book "A Panoramic View of Riemannian Geometry," by Marcel Berger.

Author Affiliations: 1Mathematical Science Research Institute, Berkeley

18. Когда наименьшее является наилучшим: как математики находят много разумных способов сделать вещи настолько маленькими (или настолько большими) насколько это возможно.

When Least Is Best: How Mathematicians Discovered Many Clever Ways to Make Things as Small (or as Large) as : Sherbert, Donald R.; O'Malley Jr., Robert E.. p188-190, 3p;

Ключевые слова: MATHEMATICIANS, NONFICTION

Reviews & Products: WHEN Least Is Best: How Mathematicians Discovered Many Clever Ways to Make Things As Small (or As Large) As Possible (Book)

People: NAHIN, Paul J.

Abstract: Reviews the book "When Least Is Best: How Mathematicians Discovered Many Clever Ways to Make Things as Small (or as Large) as Possible," by Paul J. Nahin.

19. Стохастическое интегрирование и дифференциальные уравнения. Второе издание.

Stochastic Integration and Differential Equations. Second : Sturm, Anja; O'Malley Jr., Robert E.. p190-191, 2p;

Ключевые слова: DIFFERENTIAL equations, NONFICTION

Reviews & Products: STOCHASTIC Integration & Differential Equations (Book)

People: PROTTER, Philip E.

Abstract: Reviews the book "Stochastic Integration and Differential Equations," 2nd ed., by Philip E. Protter.

Author Affiliations: 1University of Delaware

20. Дифференциальные уравнения в частных производных.

Partial Difference : Van Vleck, Erik S.; O'Malley Jr., Robert E.. p191-193, 3p;

Ключевые слова: DIFFERENTIAL equations, Partial, NONFICTION

Reviews & Products: PARTIAL Difference Equations (Book)

People: CHENG, S. S.

Abstract: Reviews the book "Partial Difference Equations," by S. S. Cheng.

Author Affiliations: 1University of Kansas

SIAM Review, 2005, Vol. 47 Issue 2,

Society for Industrial and Applied Mathematics

3600 University City Science Center | Philadelphia, PA 19104 USA

Phone: +800 | FAX: +999

Обзоры Общества промышленной и прикладной математики, том. 47,

вып. 2, 2005 год

Полный текст приводимых ниже обзоров доступен в формате.pdf

1. Обзоры и аналитика.

Survey and : LeVeque, Randy. p195, 1p;

Ключевые слова: AIRPLANES, HEADPHONES, NOISE, NOISE control, WAVE equation

Abstract: Anyone who regularly uses noise-cancelling headphones on airplanes appreciates the ability to actively control the solution to wave equations. Active control of noise over a larger scale---for example, in the entire airplane cabin---is currently being pursued by industry using actuators or smart materials. The mathematics involved in this technology raises interesting and challenging problems in control theory and numerical analysis. The Survey and Review article in this issue concerns some related mathematical problems where the goal is to drive the solution of a partial differential equation to zero by choosing an appropriate boundary condition. In simple cases the exact boundary control can be determined analytically, but for practical versions of this problem numerical methods must often be employed. A natural way to proceed is to discretize the PDE and determine the discrete control needed for the resulting discrete algebraic system. One might hope that by refining the grid, increasingly accurate approximations to the exact control needed for the PDE would be obtained. Unfortunately this is often not the case---the discrete control for the discrete system may not converge to the exact control as the mesh is refined. In the following paper, Enrique Zuazua explores this topic and the closely related issue of observability of a wave equation. While naive numerical discretization often fails, numerical methods can be applied if suitable filtering or regularization are applied, and a survey of several different approaches along these lines is also included. So put on those noise-cancelling headphones and settle down for a good read. [ABSTRACT FROM AUTHOR]

2. Распространение, наблюдение и управление волнами, аппроксимированными по методам конечных разностей.

Propagation, Observation, and Control of Waves Approximated by Finite Difference : Zuazua, Enrique, p197, 47p;

Ключевые слова: CONVERGENCE, ENGINEERING, FINITE element method, SPEED, WAVE equation

Author-Supplied Keywords: wave, finite difference approximation, propagation, observation, control, heat and beam equations

Abstract: This paper surveys several topics related to the observation and control of wave propagation phenomena modeled by finite difference methods. The main focus is on the property of observability, corresponding to the question of whether the total energy of solutions can be estimated from partial measurements on a subregion of the domain or boundary. The mathematically equivalent property of controllability corresponds to the question of whether wave propagation behavior can be controlled using forcing terms on that subregion, as is often desired in engineering applications. Observability/controllability of the continuous wave equation is well understood for the scalar linear constant coefficient case that is the focus of this paper. However, when the wave equation is discretized by finite difference methods, the control for the discretized model does not necessarily yield a good approximation to the control for the original continuous problem. In other words, the classical convergence (consistency + stability) property of a numerical scheme does not suffice to guarantee its suitability for providing good approximations to the controls that might be needed in applications. Observability/controllability may be lost under numerical discretization as the mesh size tends to zero due to the existence of high-frequency spurious solutions for which the group velocity vanishes. This phenomenon is analyzed and several remedies are suggested, including filtering, Tychonoff regularization, multigrid methods, and mixed finite element methods. We also briefly discuss these issues for the heat, beam, and Schrödinger equations to illustrate that diffusive and dispersive effects may help to retain the observability/controllability properties at the discrete level. We conclude with a list of open problems and future subjects for research. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Departmento de Matemáticas, Universidad Autónoma, 28049 Madrid, Spain

3. Проблемы и методы.

Problems and : Flaherty, Joe. P 245-246, 2p;

Ключевые слова: ALGEBRAS, Linear, ALGORITHMS, LINEAR systems, MODULES (Algebra), PARTICLES

Abstract: This issue's Problems and Techniques section contains three papers that treat areas that are simultaneously diverse and connected. The first paper considers a favorite topic in linear algebra---Krylov subspace methods, which made the widely cited "Top 10 Algorithms" (of the twentieth century) list published by Computing in Science and Engineering in January 2000. Thousands of papers have been written about these iterative techniques for solving large linear systems Ax = b. The issue considered by V. Simoncini and D. Szyld is the "superlinear convergence" of Krylov subspace methods, where the term means linear convergence that accelerates as the iterations proceed. The authors propose an analytic model of superlinear convergence derived from proximity of an invariant subspace to a crucial subspace in the algorithm. The paper contains a clear summary of previous work on analytic models of superlinear convergence; it then analyzes the convergence of specific methods, including GMRES, the conjugate gradient method, block Krylov subspace methods, and inexact Krylov subspace methods, accompanied in each case by illuminating numerical results. A particularly interesting result for inexact methods involves the effects of using invariant subspaces of the implicitly perturbed matrix rather than the original matrix. The second and third papers involve problems that might be seen as variations on a theme---the collision sequences generated by beads on a frictionless loop, and the stationary density for the traffic flow from random walks on a circle where passing is forbidden. (A visual similarity is evident in the first figures in both papers.) The second paper, by B. Cooley and P. K. Newton, studies beads on a ring. The authors note that the number of collisions is bounded for a finite number of particles colliding elastically on a line, and that several results are known for elastic particles moving in space. But on a ring there are usually an infinite... [ABSTRACT FROM AUTHOR]

4. О случае сверхлинейной сходимости точных и неточных методов подпространства Крылова.

On the Occurrence of Superlinear Convergence of Exact and Inexact Krylov Subspace : Simoncini, Valeria; Szyld, Daniel B. p 247, 26p

Ключевые слова: CONVERGENCE, FUNCTIONAL analysis, INVARIANT subspaces, MATRICES, NUMERICAL analysis

Author-Supplied Keywords: linear system, iterative method, Krylov subspace method, convergence, superlinear convergence

Abstract: Krylov subspace methods often exhibit superlinear convergence. We present a general analytic model which describes this superlinear convergence, when it occurs. We take an invariant subspace approach, so that our results apply also to inexact methods, and to nondiagonalizable matrices. Thus, we provide a unified treatment of the superlinear convergence of GMRES, conjugate gradients, block versions of these, and inexact subspace methods. Numerical experiments illustrate the bounds obtained. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Dipartimento di Matematica, Università di Bologna, Piazza di Porta S. Donato, 5, I-40127 Bologna, Italy, 2IMATI-CNR, Pavia, Italy, 3CIRSA, Ravenna, Italy, 4Department of Mathematics, Temple University (038-16),1805 N. Broad Street, Philadelphia, PA

5. Итерированная динамика воздействия N бус, скользящих по кольцу.

Iterated Impact Dynamics of N-Beads on a : Cooley, Bryan; Newton, Paul K. p273, 28p

Ключевые слова: ALGEBRA, EIGENVALUES, MATRICES, ORBITS, SPEED

Author-Supplied Keywords: eigenvalue spectra, N-beads, spectral ergodicity, impact dynamics, billiard systems, eigenvalue spectra, N –beads, spectral ergodicity, impact dynamics, billiard systems

Abstract: When N-beads slide along a frictionless hoop, their collision sequence gives rise to a dynamical system that can be studied via matrix products. It is of general interest to understand the distribution of velocities and the corresponding eigenvalue spectrum that a given collision sequence can produce. We formulate the problem for general N and state some basic theorems regarding the eigenvalues of the collision matrices and their products. The case of three beads of masses m1, m2, m3 is studied in detail. We exploit the fact that each collision sequence can be viewed as a billiard trajectory in a right triangle with non-standard reflection rules. Existence of families of periodic orbits are proven, and orbits that densely fill the triangle are computed. Eigenvalue distributions and position and velocity histograms are computed as a function of the restitution coefficient, both periodic and dense collision sequences are discussed, and a series of conjectures based on computational evidence are parisons are made between the eigenvalue distributions and autocorrelation matrices associated with dense trajectories generated from a chaotic collision sequence and spectra from matrix sequences generated from random orderings, and we describe how the three-bead system could be used as the basis for a random number generating algorithm that is computationally efficient. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Aerospace & Mechanical Engineering and Center for Applied Mathematical Sciences, University of Southern California, Los Angeles, CA

6. k Рабочих в круговом помещении склада: случайное блуждание по кругу без возможности обгона.

k Workers in a Circular Warehouse: A Random Walk on a Circle, without : Skufca,

Joseph D. p 301, 14p;

Abstract. We consider the problem of stochastic flow of multiple particles traveling on a closed loop, with a constraint that particles move without passing. We use a Markov chain description that reduces the problem to a generalized random walk on a hyperplane (with boundaries). By expressing positions via a moving reference frame, the geometry of the no-passing criteria is greatly simplified, with the resultant condition expressible as the coordinate system planes which bound the first orthant. To determine state transition probabilities, we decompose transitions into independent events and construct a digraph representation in which calculating transition probability is reduced to a shortest path determinationon the digraph. The resultant decomposition digraph is self-converse, and we exploit that property to establish the necessary symmetries to find the stationary density for the process.

7. SIGEST. p315-315, 1p; ess (Обзор направления, представляемого статьей 8)

Ключевые слова: LGORITHMS, DIFFERENTIAL equations, GEOMETRY, MATHEMATICS, MULTIGRID methods (Numerical analysis), QUANTUM chromodynamics

Abstract: Applied mathematics and scientific computation come together most beautifully when sophisticated mathematics is used to generate effective algorithms for challenging real-world problems. This combination can be even more splendid when there is a geometric underpinning to the process. Multigrid methods, which were pioneered three to four decades ago, beginning with the papers of Fedorenko in the 1960s and the seminal paper by Brandt in 1977, combine all of these aspects. Their conceptual framework, most easily understood by correspondence to finer and coarser physical grids of discretized differential equations, has led to one of the most powerful tools in scientific computation. Originally designed for elliptic partial differential equations arising in computational fluid dynamics, multigrid methods have now been extended to algebraic multigrid methods and multilevel methods that have been successfullly applied to problems in a stunningly wide range of areas, such as image reconstruction, optimization, quantum chromodynamics, and integral equations. Algebraic multigrid methods are fascinating because they provide the advantages of multigrid using an algebraic derivation, in cases where a geometric underpinning for a method is not available. As with all multigrid methods, however, they have required some knowledge or assumptions about the near-nullspace of the multigrid operator. As the problem is relaxed to coarser grids, it is crucial to the success of the method that these critical error components can be approximated accurately. The SIGEST paper in this issue, "Adpative Smoothed Aggregation ($\alpha$SA) Multigrid" by M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and *****ge, is the first paper to achieve an algebraic multigrid solver that does not require a priori knowledge of the near-nullspace of the multigrid operator. Instead, the authors show how to generate this information as part of the algorithm, through an adaptive process that... [ABSTRACT FROM AUTHOR]

8. Адаптивная сглаженная агрегация ($\alpha$SA) мультигрид.

Adaptive Smoothed Aggregation ($\alpha$SA) : Brezina, M.; Falgout, R.;

MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J.. p317, 30p;

Ключевые слова: DIFFERENTIAL equations, Partial, ENGINEERING, GEOMETRY, ITERATIVE methods (Mathematics), LINEAR system, Author-Supplied Keywords: algebraic multigrid (AMG)б generalized smoothed aggregation (SA, adaptive methodб black-box method

Abstract: Substantial effort has been focused over the last two decades on developing multilevel iterative methods capable of solving the large linear systems encountered in engineering practice. These systems often arise from discretizing partial differential equations over unstructured meshes, and the particular parameters or geometry of the physical problem being discretized may be unavailable to the solver. Algebraic multigrid (AMG) and multilevel domain decomposition methods of algebraic type have been of particular interest in this context because of their promises of optimal performance without the need for explicit knowledge of the problem geometry. These methods construct a hierarchy of coarse problems based on the linear system itself and on certain assumptions about the smooth components of the error. For smoothed aggregation (SA) multigrid methods applied to discretizations of elliptic problems, these assumptions typically consist of knowledge of the near-kernel or near-nullspace of the weak form. This paper introduces an extension of the SA method in which good convergence properties are achieved in situations where explicit knowledge of the near-kernel components is unavailable. This extension is accomplished in an adaptive process that uses the method itself to determine near-kernel components and adjusts the coarsening processes accordingly. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Department of Applied Mathematics, Campus Box 526, University of Colorado at Boulder, Boulder, CO

2Center for Applied Scientific Computation, Lawrence Livermore National Lab, P. O.Box 808, Livermore, CA 94551

9. Образование.

: Bernoff, Andrew J.; Editor, Section. p347-347, 1p;

Ключевые слова: FOREST fires, GRAPH theory, GROUNDWATER, MATHEMATICS, POLYMERS, POROUS materials, PROBABILITIES

Abstract: In mathematics, problems with exact solutions are like gold nuggets. They often allow one to illustrate the fundamental behavior of a class of problems with elegance and simplicity, and at a level the neophyte can understand. One such nugget is described in this issue's Education paper, "Critical Percolation on a Bethe Lattice Revisited" by Braga, Sanchis, and Schieber. Percolation theory lives at the intersection of graph theory and probability. The following is a typical percolation theory question: Given a porous material (such as a sponge) with a set of pores connected by channels that are randomly chosen to be open or closed, what is the probability that a pore in the center is connected to the outside boundary? (That is, what is the probability that fluid can percolate from the outside boundary to the central pore?) Questions of this type arise in numerous applications, including modeling the spread of an epidemic or a forest fire, the flow of groundwater, and the formation of polymer networks. Our paper considers percolation theory on a Bethe lattice (of which a binary tree is perhaps the most familiar example). The authors build the theory from the ground up and describe a beautiful example of what physicists call a phase transition and the associated concepts of critical probability and critical exponents. Moreover, in this model the authors describe how to compute these quantities exactly. The paper also illustrates how percolation theory can become particularly subtle as the domain size becomes infinite. This material could naturally be introduced into the undergraduate curriculum as a case-study in a discrete mathematics or a graph theory course. The paper also may kindle interest in what is an active and applied area of graduate study and research. On a more personal note, this issue commences my term as Editor of the Education section. Fortunately, my predecessor, Bobby Schnabel, is not far away - I wish him... [ABSTRACT FROM AUTHOR]

10. Критическая перколация (просачивание) на решетке Бете. Переработка более ранней публикации на тему.

Critical Percolation on a Bethe Lattice : Braga, Gastão A.; Sanchis, Rémy; Schieber,

Tiago A.. p349, 17p;

Ключевые слова: GRAPH theory, LATTICE theory, PERCOLATION, PHASE rule & equilibrium, PHASE transformations (Statistical physics).Author-Supplied Keywords: Bethe lattice, critical exponent, percolation probability, asymptotic behavior

Abstract: We introduce the model of independent percolation on general graphs with emphasis on the Bethe lattice, for which we prove the existence of a phase transition with the precise calculation of the critical value, and derive the value of the critical exponents $\gamma$ and $\b$. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Departamento de Matem´tica, UFMG, Caixa Postal 1621, , Belo Horizonte, MG, Brazil

11. Обзор книг.

Book : O'Malley, Bob. p367, 37p;

Reviews & Products: MOST Honourable Remembrance: The Life & Work of Thomas Bayes (Book)

COMBINATORICS of Permutations (Book)

STATISTICS & Finance: An Introduction (Book)

INTRODUCTION to the Mathematics of Finance: From Risk Management to Options Pricing (Book)

STOCHASTIC Calculus for Finance: The Binomial Asset Pricing Model (Book)

STOCHASTIC Calculus for Finance: Continuous-Time Models (Book)

Abstract: This issue's featured review, by Ronnie Sircar of Princeton University, concerns books that introduce students to the mathematics of finance. The popularity and demand for the topic seems to be mushrooming, and publishers are responding with a wide variety of new texts. Our readers know that math is central to many new developments, but it's welcome to find that our brightest graduates are now in demand on Wall Street. This may even increase their value at universities and elsewhere. Many of the individual book reviews emphasize history, a natural way to understand how our subject evolves. The review of Peter Lax's Functional Analysis points out that Banach's body was used in a concentration camp to raise lice. Such awful, but unforgettable, examples make us realize that the context in which math is created is essential to pass on. We thank our reviewers for their valuable opinions. [ABSTRACT FROM AUTHOR]

Author Affiliations: 1Princeton Universityб 2University of Puget Sound, 3University of Waikato, Hamilton, New Zealand, 4University of Pittsburgh, 5Colorado State University, 6University of Arizona, 7Clarkson University, 8University of Manchester, 9Washington University, St. Louis, 10University of Queensland, Australia, 11University of Washington, 12University of Albert, 13Universität Hamburg, 14Brown University

15Rutgers University, 16University of Central Florida, 17University of San Francisco, 18Southern Illinois University at Carbondale, 19Duke University