bluuebunny/crossref_metadata_2025 huggingface dataset:
STUDIES OF CLEAN METAL SURFACE RELAXATION EXPERIMENT–THEORY DISCREPANCIES
Authors: TEETER G. , ERSKINE J. L.
Published: July 2002

A series of Low-Energy Electron Diffraction Intensity vs. Voltage (LEED I–V) measurements for Rh(001), W(110) and Ti(0001) have been undertaken in order to help resolve discrepancies between experiment and theory for the surface relaxations of certain transition metals. LEED measurements and analysis indicate the following results for the change of first (d12) and second (d23) interlayer spacings, relative to the bulk interlayer spacing d0: for Rh(001), Δ d12/d0=-1.4± 1.4% and Δ d23/d0=-0.6± 1.4%; for W(110), Δ d12/d0=-3.0± 1.3% and Δ d23/d0=+0.2± 1.3%; and for Ti(0001), Δ d12/d0=-4.9± 1.0% and Δ d23/d0=+1.4± 1.0%. In each case, the new measurements help to resolve the experiment–theory surface relaxation discrepancies. In addition, two of these surfaces [W(110) and Ti(0001)] show substantial contractions in the first interlayer spacing, d12. Large relaxations for close-packed surfaces lend support to the promotion–hybridization picture of surface relaxation put forth recently by P. J. Feibelman [P. J. Feibelman, Phys. Rev.B53, 13740 (1996).] In addition to making new experimental determinations of surface relaxations, a secondary goal of this work is to characterize sources of error associated with LEED I–V methodology that have traditionally not been fully appreciated.
MODEL ON SIZE/TYPE CONVERSION OF STACKING-FAULTED HALF ON QUENCHED Si(111) SURFACE
Authors: KATO T. , UCHIBE M. , SHIMADA W. , TOCHIHARA H.
Published: July 2002

Recent revelation on even-sized stacking-faulted halves as well as irregular odd-sized ones on the quenched Si(111) surface is theoretically studied. The employed model for the analysis is an extended version of the cell model which was proposed to interpret the phase transition of the 7×7 structure in terms of the formation energy of each element of the DAS structure. The probability distributions of the various sizes/types of stacking-faulted halves are calculated in corresponding situations of the experiment. The calculated probability distributions are qualitatively coincident with the experimental result.
STRUCTURE OF CHEMICALLY PREPARED PASSIVATION LAYERS ON SINGLE CRYSTAL SEMICONDUCTOR SURFACES
Authors: HITCHCOCK A. P. , TYLISZCZAK T. , BRODERSEN P. , LU Z. H. , DHARMA-WARDANA M. W. C.
Published: July 2002

Monolayers of S and Cl have useful passivation properties for group IV and III–V semiconductor surfaces. The structures of Ge(111)–Cl; GaAs(111)–Cl; GaAs(111)A–S, GaAs(111)B–S and GaAs(001)–S monolayer-passivated single crystal semiconductor surfaces have been studied using synchrotron radiation X-ray absorption fine structure spectroscopy (XAFS). The near edge and extended fine structure signals are interpreted using comparisons to multiple scattering XAFS calculations and, in the cases of Ge(111)–Cl and GaAs(111)–Cl, comparison to first-principles calculations. Relationships between the surface structure and the development of improved passivated surfaces are discussed.
THE ACCESSORY NERVE AND THE CERVICAL PLEXUS: ANATOMY AND CLINICAL IMPLICATIONS
Authors: Wu Wing-Cheung , Lam Ying-Lee , Chang Yun-Po , Poon Kai-Chung , Au Kin-Ming
Published: July 2002

The accessory nerve and the motor branch of the cervical plexus have been used as donor nerves in neurotisation procedures for brachial plexus palsy. However, there are few reports in the literature that describe their anatomy in detail. The aim of this study is to delineate the applied anatomy of these nerves. We emphasise their course in the posterior triangle of the neck as well as within the trapezius muscle. Fourteen cadavers were dissected. We identified nerves not reported before and they are the lateral cutaneous branches of C3 and C4. The deep branch of C4 is present in all the cases; it supplies the trapezius muscle and we believe it contains motor fibres. The accessory nerve gives a branch in the neck in only one case. The accessory nerve joins the deep branch of C4 in 93.3% of the cases. Clinical implications of the findings would be discussed.
THE EFFECTS OF CIGARETTE SMOKING ON RABBIT TIBIAL VASCULAR ENDOTHELIUM
Authors: TU YUAN-KUN , UENG STEVE WEN-NENG
Published: July 2002

Cigarette smoking is hazardous for various tissues in human. The cigarette smoke inhalation has been proved to delay bone healing. However, no previous study demonstrates the smoking effect on bony microcirculation. In this study, we investigated the effect of cigarette smoking on tibial vascular endothelium and blood flow by using the bone chamber model.

Eighteen adult New Zealand rabbits were divided into 3 groups. Group 1: Control, Group 2: 1 week smoking, and Group 3: 6 weeks smoking. All these rabbits were then anesthetized, and their nutrient arteries of tibia were identified and cannulated. We put the tibia into bone chamber after cannulation, perfused with Krebs-Ringer solution (phase 1), and then compared the effect of vasospasm by norepinephrine dose-response curve (NEDRC). Acetylcholine (phase 2) and L-NMMA (phase 3) were also perfused and the NEDRC recorded. Acetylcholine can stimulate the release of nitric oxide and lower the NEDRC. L-NMMA inhibits NO synthesis in vascular endothelium, and hence results in vasoconstriction under various stimuli. Data collection and statistic processing were performed by ANOVA analysis.

The NEDRC data in Group 1 (control) was set to be 100%. In phase 1 study, our results showed that 1 week cigarette smoking significantly increased NEDRC in Group 2 (142.5%, p<0.01). However, 6 weeks smoking strikingly boosted the response of NEDRC in Group 3 (226.5%, p<0.01). In phase 2 study, Group 2 tibia showed the NEDRC under acetylcholine perfusion to be without any difference in comparison with Group 1 (p>0.05). Nevertheless, Group 3 tibia showed significant vasospasm even under acetylcholine perfusion. In phase 3 study, L-NMMA perfused data revealed that; Group 3 tibia had the highest NEDRC, i.e. the most severe vasospasm.

Based on our study, both short-term and long-term cigarette smoking are hazardous to the bony vascular endothelium. The nitric oxide production significantly attenuated in Group 2 and 3 tibia. However, the adverse effect of smoking seems reversible in short-term (Group 2). Long-term smoking (Group 3) causes irreversible damage to vascular endothelium and muscarinic receptor.
A MULTI-AGENT MODELLING ENVIRONMENT FOR MARKET SIMULATION
Authors: FLETCHER-HOLMES DAVID , TROWELL STEPHEN
Published: July 2002

We present a modelling environment for the simulation of interactions between agents of different strategies similar to that reported by Lux (Nature 397 1999). Our freely available software allows market parameters to be adjusted via a simple interface. The incorporation of different population size distributions extends previous work.
OPTIMAL TRADING STRATEGY WITH PARTIAL INFORMATION AND THE VALUE OF INFORMATION: THE SIMPLIFIED AND GENERALIZED MODELS
Authors: YANG ZHAOJUN , MA CHAOQUN
Published: July 2002

In this paper we deal with the optimization problem of maximizing the expected total utility from consumption under the case of partial information. By means of the martingale method and filter theory, we have acquired an explicit solution to optimal investment and consumption determined by the security prices for a special security price process. Furthermore, we establish a simple formula for valuing information, provided that the utility function is logarithmic. In the end, we extend most of the conclusions to a general situation where both the interest rate and dispersion coefficient of risk security follow some stochastic processes.
CHARACTERISATION OF LINEAR MINI-MAX ESTIMATORS FOR LOSS FUNCTIONS OF ARBITRARY POWER
Authors: HELMES K. , SRINIVASAN C.
Published: July 2002

Let Y(t), t∈[0,1], be a stochastic process modelled as dYt=θ(t)dt+dW(t), where W(t) denotes a standard Wiener process, and θ(t) is an unknown function assumed to belong to a given set Θ⊂L2[0,1]. We consider the problem of estimating the value ℒ(θ), where ℒ is a continuous linear function defined on Θ, using linear estimators of the form =∫m(t)dY(t), m∈L2[0,1]. The distance between the quantity ℒ(θ) and the estimated value is measured by a loss function. In this paper, we consider the loss function to be an arbitrary even power function. We provide a characterisation of the best linear mini-max estimator for a general power function which implies the characterisation for two special cases which have previously been considered in the literature, viz. the case of a quadratic loss function and the case of a quartic loss function.
PERFORMANCE MODELLING OF PIPELINED CIRCUIT SWITCHING UNDER MMPP TRAFFIC
Authors: MIN GEYONG , OULD-KHAOUA MOHAMED
Published: July 2002

Performance properties of switching methods used in existing interconnection networks have been mainly examined under the assumption that network traffic follows the Poisson arrival process. However, the Poisson process is unable to capture the bursty nature of traffic. In this paper we propose the first analytical model for pipelined circuit switching under bursty traffic using the Markov-Modulated Poisson Process (MMPP). Simulation experiments reveal that the proposed model exhibits a good degree of accuracy for various networks sizes and under different traffic conditions.
FAST RENDERING WATER SURFACE FOR OUTDOOR SCENES
Authors: TADAMURA KATSUMI , QIN XUEYING , JIAO GUOFANG , NAKAMAE EIHACHIRO
Published: July 2002

Water surface is an important element for rendering a realistic landscape image, particularly for visual environmental assessment. The incident light from the water surface to the viewpoint generally consists of two components, reflected and refracted light. The source of the latter is further subdivided into reflected light from the bottom of the water and scattered light in it. In order to render a realistic water surface, the calculation for each component of the light is a quite complex and time consuming task. We propose the fast rendering algorithms of the water surface for visual environmental assessment of outdoor scenes. The features are: (1) the reflected light from the water surface is rendered very quickly through the quasi-ray tracing techniques, which employ inversion and reflection mapping with consideration of the depth of objects mirrored on the water surface; (2) the refracted light coming through the water surface, which gives the color of water, is efficiently calculated by using a look-up table in which both characteristics of the light sources (both direct sunlight and skylight) and the effects of scattering and attenuation depending on turbidity are taken into account. In order to testify the proposed algorithms, some examples are given.
PAGE SEGMENTATION AND CLASSIFICATION UTILIZING BOTTOM-UP APPROACH
Authors: AMIN ADNAN , SHIU RICKY
Published: July 2002

Document image processing has become an increasingly important technology in the automation of office documentation tasks. Automatic document scanners such as text readers and OCR (Optical Character Recognition) systems are an essential component of systems capable of those tasks. One of the problems in this field is that the document to be read is not always placed correctly on a flat-bed scanner. This means that the document may be skewed on the scanner bed, resulting in a skewed image. This skew has a detrimental effect on document analysis, document understanding, and character segmentation and recognition. Consequently, detecting the skew of a document image and correcting it are important issues in realizing a practical document reader. This paper presents the use of analyzing the connected components extracted from the binary image of a document page. Such an analysis provides a lot of useful information, and will be used to perform skew correction, segmentation and classification of the document. Moreover, we describe two new algorithms — one for skew detection and one for skew correction. The new skew correction algorithm we propose has been shown to be fast and accurate, with run times averaging under 1.5 CPU seconds and 30 seconds real time to calculate the angle on a 5000/20 DEC workstation. Experiments on over 100 pages show that the method works well on a wide variety of layouts, including sparse textual regions, mixed fonts, multiple columns, and even for documents with a high graphical content.
LEARNING OF FUZZY AUTOMATA
Authors: PEDRYCZ WITOLD , GACEK ADAM
Published: July 2002

In this study, we revisit the well-known notion of fuzzy state machines and discuss their development through learning. The systematic development of fuzzy state machines has not been pursued as intensively as it could have been expected from the breadth of the possible usage of them as various modelling platforms. We concentrate on the generalization of the well known architectures exploited in Boolean system synthesis, namely Moore and Mealy machines and show how these can be implemented in terms of generic functional modules such as fuzzy JK flip-flops and fuzzy logic neurons (AND and OR neurons) organized in the form of logic processors. It is shown that the design of the fuzzy state machines can be accomplished through their learning. The detailed learning algorithm is presented and illustrated with a series of numeric examples. The study reveals an interesting option of constructing digital systems through learning: the original problem is solved in the setting of fuzzy state machines and afterwards "binarised" into the two-valued format realized via the standard digital hardware.
CO-EVOLUTION IN SOCIAL INTERACTIONS
Authors: SATO HIROSHI , NAMATAME AKIRA
Published: July 2002

An interesting problem which has been widely investigated is under what circumstances will a society of rational agents realize some particular stable situations, and whether they satisfy the condition of social efficiency? This will crucially depend on how they interact and what information they have when they interact. For instance, when strategic interactions are modeled as coordination games, it is known the evolutionary process selects the risk-dominant equilibrium which is not necessarily efficient. We consider the networks of agents, in which each agent faces several types of the strategic decision problems. We investigate the dynamics of collective decision when each agent adapts the strategy of interaction to its neighbors. We are interested in to show how the society gropes its way towards an equilibrium situation. We show that the society selects the most efficient equilibrium among multiple equilibria when the agents composing it do learn from each other as collective learning, and they co-evolve their strategies over time. We also investigate the mechanism that leads the society to an equilibrium of social efficiency.
Supercomputing policy links science and the “C” word
Authors: Crawford Diane
Published: July 2002

Competition, a concept nary whispered in pure science circles, might just have been the catalyst that finally drove the High Performance Computing and Communication (HPCC) policy over the Hill. It has taken many years, and countless government studies, to help legislators even comprehend and appreciate the potential of high-performance computing technology in the U.S. But toss in the competitive angle, and the story needs little translation.
Precise and efficient integration of interprocedural alias information into data-flow analysis
Authors: Burke Michael , Choi Jong-Deok
Published: July 2002

Data-flow analysis is a basis for program optimization and parallelizing transformations. The mechanism of passing
reference
parameters at call sites generates
interprocedural aliases
which complicate this analysis. Solutions have been developed for efficiently computing interprocedural aliases. However, factoring the computed aliases into data-flow information has been mostly overlooked, although improper factoring results in imprecise (conservative) data-flow information. In this document, we describe a mechanism which, in factoring in interprocedural aliases, computes data-flow information more precisely and with less time and space overhead than previous approaches.
Twisted GFSR generators
Authors: Matsumoto Makoto , Kurita Yoshiharu
Published: July 2002

The generalized feed back shift register (GFSR) algorithm suggested by Lewis and Payne is a widely used pseudorandom number generator, but has the following serious drawbacks: (1) an initialization scheme to assure higher order equidistribution is involved and is time consuming; (2) each bit of the generated words constitutes an
m
-sequence based on a primitive trinomials, which shows poor randomness with respect to weight distribution; (3) a large working area is necessary; (4) the period of sequence is far shorter than the theoretical upper bound. This paper presents the twisted GFSR (TGFSR) algorithm, a slightly but essentially modified version of the GFSR, which solves all the above problems without loss of merit. Some practical TGFSR generators were implemented and passed strict empirical tests. These new generators are most suitable for simulation of a large distributive system, which requires a number of mutually independent pseudorandom number generators with compact size.
A test for cancellation errors in quasi-Newton methods
Authors: Gurwitz Chaya
Published: July 2002

It has recently been shown that cancellation errors in a quasi-Newton method can increase without bound as the method converges. A simple test is presented to determine when cancellation errors could lead to significant contamination of the approximating matrix.
Updating relational databases through weak instance interfaces
Authors: Atzeni Paola , Torlone Riccardo
Published: July 2002

The problem of updating databases through interfaces based on the weak instance model is studied, thus extending previous proposals that considered them only from the query point of view. Insertions and deletions of tuples are considered.

As a preliminary tool, a lattice on states is defined, based on the information content of the various states.

Potential results of an insertion are states that contain at least the information in the original state and that in the new tuple. Sometimes there is no potential result, and in the other cases there may be many of them. We argue that the insertion is deterministic if the state that contains the information common to all the potential results (the greatest lower bound, in the lattice framework) is a potential result itself. Effective characterizations for the various cases exist.

A symmetric approach is followed for deletions, with fewer cases, since there are always potential results; determinism is characterized as a consequence.
Design and verification of the Rollback Chip using HOP
Authors: Gopalakrishnan Ganesh , Fujimoto Richard
Published: July 2002

The use of formal methods in hardware design improves the quality of designs in many ways: it promotes better understanding of the design; it permits systematic design refinement through the discovery of invariants; and it allows design verification (informal or formal). In this paper we illustrate the use of formal methods in the design of a custom hardware system called the “Rollback Chip” (RBC), conducted using a simple hardware design description language called “HOP”. An informal specification of the requirements of the RBC is first given, followed by a
behavioral description
of the RBC stating its
desired behavior
. The behavioral description is refined into progressively more efficient designs, terminating in a
structural description
. Key refinement steps are based on system invariants that are discovered during the design, and proved correct during design verification. The first step in design verification is to apply a program called PARCOMP to
derive
a behavioral description from the structural description of the RBC. The derived behavior is then compared against the desired behavior using equational verification techniques. This work demonstrates that formal methods can be fruitfully applied to a nontrivial hardware design. It also illustrates the particular advantages of our approach based on HOP and PARCOMP. Last, but not the least, it formally verifies the RBC mechanism itself.
Unified compilation of Fortran 77D and 90D
Authors: Choudhary Alok , Fox Geoffrey , Hiranandani Seema , Kennedy Ken , Koelbel Charles , Ranka Sanjay , Tseng Chau-Wen
Published: July 2002

We present a unified approach to compiling Fortran 77D and Fortran 90D programs for efficient execution of MIMD distributed-memory machines. The integrated Fortran D compiler relies on two key observations. First, array constructs may be
scalarized
into FORALL loops without loss of information. Second,
loop fusion, partitioning,
and
sectioning
optimizations are essential for both Fortran D dialects.
Computing bounds on steady state availability of repairable computer systems
Authors: Lui John C. S. , Muntz Richard R.
Published: July 2002

One of the most important performance measures for computer system designers is system availability. Most often, Markov models are used in representing systems for dependability/availability analysis. Due to complex interactions between components and complex repair policies, the Markov model often has an irregular structure, and closed-form solutions are extremely difficult to obtain. Also, a realistic system model often has an unmanageably large state space and it quickly becomes impractical to even generate the entire transition rate matrix. In this paper, we present a methodology that can (i) bound the system steady state availability and at the same time, (ii) drastically reduce the state space of the model that must be solved. The bounding algorithm is iterative and generates a part of the transition matrix at each step. At each step, tighter bounds on system availability are obtained. The algorithm also allows the size of the submodel, to be solved at each step, to be chosen so as to accommodate memory limitations. This general bounding methodology provides an efficient way to evaluate dependability models with very large state spaces without ever generating the entire transition rate matrix.
Algorithm 738: a software package for unconstrained optimization using tensor methods
Authors: Chow T. , Eskow E. , Schnabel R.
Published: July 2002

This paper describes a software package for finding the unconstrained minimizer of a nonlinear function of
n
variables. The package is intended for problems where
n
is not too large—say,
n
100—so that the cost of storing one
n
×
n
matrix, and factoring it at each iteration, is acceptable. The software allows the user to choose between a recently developed “tensor method” for unconstrained optimization and an analogous standard method based on a quadratic model. The tensor method bases each iteration on a specially constructed fourth-order model of the objective function not significantly more expensive to form, store, or solve than the standard quadratic model. In our experience, the tensor method requires significantly fewer iterations and function evaluations to solve most unconstrained optimization problems than standard methods based on quadratic models, and also solves a somewhat wider range of problems. For these reasons, it may be a useful addition to numerical software libraries.
Computing the

MDM
T

decomposition
Authors: Kaufman Linda
Published: July 2002

The

MDM
T

factorization of an
n×n
symmetric indefinite matrix
A
can be used to solve a linear system with
A
as the coefficient matrix. This factorization can be computed efficiently using an algorithm given in 1977 by Bunch and Kaufman. The LAPACK project has been implementing block versions of well-known algorithms for solving dense linear systems and eigenvalue problems. The block version of the

MDM
T

decomposition algorithm in LAPACK requires the user to specify a block size
b
by supplying an
n×b
scratch array. It then makes (
n/b
−2)
2
/2 invocations of a matrix-matrix product subroutine with one matrix no larger than
b×b, n
2
/(2
b
)−
b
invocations of a matrix-vector product routine with a matrix no larger than
b×b
, and between
n
−
n/b
and 2(
n
−
n/b
) invocations of a matrix-vector product routine with matrices with less than
b
columns. Because the user can query LAPACK about an optimal block size, our concern is focused on users who cannot change the amount of available scratch space or who neglect to use this facility and are unaware of a performance degradation with small block sizes. This article suggests two alternative algorithms. The first is a block algorithm requiring
b×b
scratch space and is about 5% slower than LAPACK's current block algorithm with large
b
. The user does not have to specify the block size. The second algorithm is a rejuvenation of an old implementation of the

MDM
T

decomposition algorithm that requires
n
matrix-vector products. The performance of the various algorithms on a specific machine is dependent on the manufacturer's implementation of the different basic linear algebra subroutines that they each invoke. Our data indicate that on the Cray Y-MP, Alliant, and Convex the time for the rejuvenated algorithm is either less than or within 10% of that of LAPACK's block algorithm with large
b
.
Automatic correction to misspelled names
Authors: Bickel Michael Allen
Published: July 2002

Using an information theoretic likeness measure defined as an inner product on a data space created from a table of valid names, this 4GL procedure searches the database space for the nearest correctly spelled name.
Prolog in 10 figures
Authors: Colmerauer Alain
Published: July 2002

In the fall of 1981, a Japanese report officially initiated the quest for fifth-generation computers that would encompass the functions of knowledge processing and artificial intelligence. The conceptual underpinnings behind Prolog—Japan's language of choice for these activities—are presented here in a way that suggests why Prolog or a similar language might be considered a model for designing the computers of the future.
Document ranking on weight-partitioned signature files
Authors: Lee Dik Kun , Ren Liming
Published: July 2002

A signature file organization, called the weight-partitioned signature file, for supporting document ranking is proposed. It employs multiple signature files, each of which corresponds to one term frequency, to represent terms with different term frequencies. Words with the same term frequency in a document are grouped together and hashed into the signature file corresponding to that term frequency. This eliminates the need to record the term frequency explicitly for each word. We investigate the effect of false drops on retrieval effectiveness if they are not eliminated in the search process. We have shown that false drops introduce insignificant degradation on precision and recall when the false-drop probability is below a certain threshold. This is an important result since false-drop elimination could become the bottleneck in systems using fast signature file search techniques. We perform an analytical study on the performance of the weight-partitioned signature file under different search strategies and configurations. An optimal formula is obtained to determine for a fixed total storage overhead the storage to be allocated to each partition in order to minimize the effect of false drops on document ranks. Experiments were performed using a document collection to support the analytical results.
Mobile UNITY
Authors: Roman Gruia-Catalin , McCann Peter J. , Plun Jerome Y.
Published: July 2002

Mobile computing represents a major point of departure from the traditional distributed-computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns present designers with unprecedented challenges in the areas of modularity and dependability. So far, the literature on mobile computing is dominated by concerns having to de with the development of protocols and services. This article complements this perspective by considering the nature of the underlying formal models that will enable us to specify and reason about such computations. The basic research goal is to characterize fundamental issues facing mobile computing. We want to achieve this in a manner analogous to the way concepts such as shared variables and message passing help us understand distributed computing. The pragmatic objective is to develop techniques that facilitate the verification and design of dependable mobile systems. Toward this goal we employ the methods of UNITY. To focus on what is essential, we center our study on
ad hoc networks
, whose singular nature is bound to reveal the ultimate impact of movement on the way one computes and communicates in a mobile environment. To understand interactions we start with the UNITY concepts of union and superposition and consider direct generalizations to transient interactions. The motivation behind the transient nature of the interactions comes from the fact that components can communicate with each other only when they are within a a certain range. The notation we employ is a highly modular extension of the UNITY programming notation. Reasoning about mobile computations relies on extensions to the UNITY proof logic.
Phong normal interpolation revisited
Authors: van Overveld C. W. A. M. , Wyvill B.
Published: July 2002

Phong shading is one of the best known, and at the same time simplest techniques to arrive at realistic images whem rendering 3D geometric models. However, despite (or maybe due to) its success and its widespread use, some aspects remain to be clarified with respect to its validity and robustness. This might be caused by the fact that the Phong method is based on geometric arguments, illumination models, and clever heuristics. In this article we address some of the fundamentals that underlie Phong shading, such as the computation of vertex normals for nonmanifold models and the adequacy of linear interpolation and we apply a new interpolation technique to achieve an efficient and qualitatively improve result.
Level 3 basic linear algebra subprograms for sparse matrices
Authors: Duff Iain S. , Marrone Michele , Radicati Giuseppe , Vittoli Carlo
Published: July 2002

This article proposes a set of Level 3 Basic Linear Algebra Subprograms and associated kernels for sparse matrices. A major goal is to design and develop a common framework to enable efficient, and portable, implementations of iterative algorithms for sparse matrices on high-performance computers. We have designed the routines to shield the developer of mathematical software from most of the complexities of the various data structures used for sparse matrices. We have kept the interface and suite of codes as simple as possible while at the same time including sufficient functionality to cover most of the requirements of iterative solvers and sufficient flexibility to cover most sparse matrix data structures. An important aspect of our framework is that it can be easily extended to incorporate new kernels if the need arises. We discuss the design, implementation, and use of subprograms for the multiplication of a fully matrix by a sparse one and for the solution of sparse triangular systems with one or more (full) right-hand sides. We include a routine for checking the input data, generating a new sparse data structure from the input, and scaling a sparse matrix. The new data structure for the transformation can be specified by the user or can be chosen automatically by vendors to be efficient on their machines. We also include a routine for permuting the columns of a sparse matrix and one for permuting the rows of a full matrix.
Algorithms for degree-raising of splines
Authors: Cohen Elaine , Lyche Tom , Schumaker Larry L.
Published: July 2002

Stable and efficient algorithms for degree-raising of curves (or surfaces) represented as arbitrary B-splines are presented as a application of the solution to the theoretical problem of rewriting a curve written as a linear combination of
m
th order B-splines as a linear combination of (
m
+ 1)st order B-splines with a minimal number of knot insertions. This approach can be used to introduce additional degrees of freedom to a curve (or surface), a problem which naturally arises in certain circumstances in constructing mathematical models for computer-aided geometric design.
Sampling procedural shaders using affine arithmetic
Authors: Heidrich Wolfgang , Slusallek Philipp , Seidel Hans-Peter
Published: July 2002

Procedural shaders have become popular tools for describing surface reflectance functions and other material properties. In comparison to fixed resolution textures, they have the advantage of being resolution-independent and storage-efficient.

While procedural shaders provide an interface for evaluating the shader at a single point, it is not easily possible to obtain an average value of the shader together with accurate error bounds over a finite area. Yet the ability to compute such error bounds is crucial for several interesting applications, most notably heirarchical area sampling for global illumination, using the finite element approach, and for generation of textures used in interactive computer graphics.

Using affine arithmetic for evaluating the shader over a finite area yields a tight, conservative error interval for the shader function. Compilers can automatically generate code for utilizing affine arithmetic from within shaders implemented in a dedicated language such as the RenderMann shading language.
Remark on algorithm 622
Authors: Levin Stewart A.
Published: July 2002

A number of updates to the macroprocessor are described that bring the code into line with the Fortran 77 standard. This is followed by an outline of how the macroprocessor was used for the rapid porting of geophysical software from a 64-bit supercomputer environment to a number of different Unix workstations. Finally a number of deficiencies remaining in the macroprocessor are noted and workarounds suggested where possible.
Information gathering in the World-Wide Web
Authors: Konopnicki David , Shmueli Oded
Published: July 2002

The World Wide Web (WWW) is a fast growing global information resource. It contains an enormous amount of information and provides access to a variety of services. Since there is no central control and very few standards of information organization or service offering, searching for information and services is a widely recognized problem. To some degree this problem is solved by “search services,” also known as “indexers,” such as Lycos, AltaVista, Yahoo, and others. These sites employ search engines known as “robots” or “knowbots” that scan the network periodically and form text-based indices. These services are limited in certain important aspects. First, the structural information, namely, the organization of the document into parts pointing to each other, is usually lost. Second, one is limited by the kind of textual analysis provided by the “search service.” Third, search services are incapable of navigating “through” forms. Finally, one cannot prescribe a complex database-like search. We view the WWW as a huge database. We have designed a high-level SQL-like language called W3QL to support effective and flexible query processing, which addresses the structure and content of WWW nodes and their varied sorts of data. We have implemented a system called W3QS to execute W3QL queries. In W3QS, query results are declaratively specified and continuously maintained as views when desired. The current architecture of W3QS provides a server that enables users to pose queries as well as integrate their own data analysis tools. The system and its query language set a framework for the development of database-like tools over the WWW. A significant contribution of this article is in formalizing the WWW and query processing over it.
An extended owner-coupled set data model and predicate calculus for database management
Authors: Bradley J.
Published: July 2002

A data model is presented, based on the extension of the concept of a DBTG owner-coupled set to permit
static
and
dynamic
sets and a new kind of set referred to as a
virtual
set. The notion of
connection fields
is introduced, and it is shown how connection fields may be used to construct derived information bearing set names, and hence permit the specification of (dynamic) sets which are not predeclared in a schema. Virtual sets are shown to reflect the functional dependencies which can exist within a file. A technique which permits the data model to be fully described diagrammatically by
extended Bachman diagrams
is described. A predicate calculus for manipulation of this data model is presented. Expressions written in this calculus are compared with corresponding expressions in a relational predicate calculus, DSL ALPHA. An argument for the relational completeness of the language is given.
Concurrent manipulation of binary search trees
Authors: Kung H. T. , Lehman Philip L.
Published: July 2002

The concurrent manipulation of a binary search tree is considered in this paper. The systems presented can support any number of concurrent processes which perform searching, insertion, deletion, and rotation (reorganization) on the tree, but allow any process to lock only a constant number of nodes at any time. Also, in the systems, searches are essentially never blocked. The concurrency control techniques introduced in the paper include the use of special nodes and pointers to redirect searches, and the use of copies of sections of the tree to introduce many changes simultaneously and therefore avoid unpredictable interleaving. Methods developed in this paper may provide new insights into other problems in the area of concurrent database manipulation.
A Procedure for the Diagonalization of Normal Matrices
Authors: Goldstine H. H. , Horwitz L. P.
Published: July 2002

The so-called Jacobi Procedure is extended to the case of normal matrices. A stable iterative procedure is described utilizing plane unitary transformations for such matrices which yield both the characteristic values and their associated vectors. Generally, the technique consists of minimizing at each stage the sum of the squares of the off-diagonal elements of the given matrix; however, there is one case in which this leads to no improvement; i.e. the lowest value for the change is non-negative. In this case, it is shown that a convergent procedure is still possible.
Path Detection in Multidimensional Iterative Arrays
Authors: Waite William M.
Published: July 2002

An iterative array is defined as an infinite set of identical blocks, interconnected in a regular manner. Each block has inputs and outputs, with internal connections from certain inputs to certain outputs. This paper is concerned with the problem of determining, for a given structure internal to each block, the existence of a given path. The path is specified by the relative positions in the array of its endpoints, and the algorithm presented decides whether such a path is possible in the given array. A special case of the general procedure, which tests for a closed path, has been successfully programmed.
Error Bounds for Zeros of a Polynomial Based Upon Gerschgorin's Theorems
Authors: Smith Brian T.
Published: July 2002

Given
N
approximations to the zeros of an
N
th-degree polynomial,
N
circular regions in the complex
z
-plane are determined whose union contains all the zeros, and each connected component of this union consisting of
K
such circular regions contains exactly
K
zeros. The bounds for the zeros provided by these circular regions are not excessively pessimistic; that is, whenever the approximations are sufficiently well separated and sufficiently close to the zeros of this polynomial, the radii of these circular regions are shown to overestimate the errors by at most a modest factor simply related to the configuration of the approximations. A few numerical examples are included.
The Equivalence Problem of Simple Programs
Authors: Tsichritzis D.
Published: July 2002

Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been proved to be unsolvable for the class
L
2
of loop programs defining the class of elementary functions. A solution is given for the class
L
1
defining the class of simple functions. Further, a set of other decision problems not directly connected with the equivalence problem is investigated. These problems are found again to be unsolvable for the class
L
2
; but as before, a solution is given for the class
L
1
. It is concluded, therefore, that there is a barrier of unsolvability between the classes
L
1
and
L
2
.
A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
Authors: Hirschberg D. S. , Wong C. K.
Published: July 2002

The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed
n
> 2, the knapsack problem with
n
variables can be solved in polynomial time.
Array Permutation by Index-Digit Permutation
Authors: Fraser Donald
Published: July 2002

An array may be reordered according to a common permutation of the digits of each of its element indices. The digit-reversed reordering which results from common fast Fourier transform (FFT) algorithms is an example. By examination of this class of permutation in detail, very efficient algorithms for transforming very long arrays are developed.
Compilability and compact representations of revision of Horn knowledge bases
Authors: Liberatore Paolo
Published: July 2002

Several methods have been proposed as an attempt to deal with dynamically changing scenarios. From a computational point of view, different formalisms have different computational properties. In this article we consider knowledge bases represented as sets of Horn clauses. The importance of this case is twofold: first, inference is polynomial, thus tractable; second, Horn clauses represents causal relations between facts, thus they are of great practical importance, although not all propositional knowledge bases can be represented in Horn form. The complexity of Horn revision is still high, and in some cases coincides with the complexity of the general (non-Horn) case. We analyze the complexity of belief revision from the point of view of the compilation [Cadoli et al. 1999]: we study the possibility of reducing the complexity by allowing a (possibly expensive) preprocessing of part of the input of the problem. Extending the work of Cadoli et al.[1996], we consider the problem of compact representation of revision in the Horn case, i.e., given a knowledge base
T
and an update
P
(both represented by Horn clauses) decide whether
T * P
, the result of the revision, can be represented with a propositional formula whose size is polynomial in the size of
T
and
P
. We give this representation for all formalisms for which it exists, and we show that the existence of a compact representation is related to the possibility of decreasing the complexity of a formalism via a proprocessing.
Redundancy in model specifications for discrete event simulation
Authors: Nance Richard E. , Overstreet C. Michael , Page Ernest H.
Published: July 2002

Although redundancy in model specification generally has negative connotations, we offer arguments for revising those convictions. Defining “representational redundancy” as the inclusion of any symbols not required to fulfill the study objectives, we cite several sources of redundancy, classified as accidental or intentional, that contribute positively to the model development tasks. Comparative benefits and detriments are discussed briefly. Focusing on the most interesting source of redundancy‐that which is intentionally induced by a modeling methodology—we demonstrate that automated elimination of redundancy can actually improve model execution time. Using four models drawn from the literature that are easily understood, but which represent some differences in size and complexity, the direct graphical representations shows improvements over a base case ranging from 27.3 percent to 68.1 percent in execution time. Further, increasing improvement is realized with increasing model size and complexity. These results are encouraging because they suggest that modeling methodologies with automated model diagnosis can significantly reduce both execution and developments time and cost.
Remark on Algorithm 761
Authors: de Tisi Flavia , Valtulina Alba
Published: July 2002

Several improvements to the estimation of partial derivatives in Algorithm 761 are presented. The problems corrected are (1) in the calculation of the probability weight in subroutine SDPD3P which may result in overflow, (2) in the calculation of final weight in subroutine SDPD3P which may result in overflow, (3) in the computation of a determinant in subroutine SDLEQN which is not necessary, and (4) in the computation of the condition number of a matrix in subroutine SDLEQN which generates very different results for matrices that differ only in row order.
Mark sense and port-a-punch programming inputs
Authors: Luebbert William F.
Published: July 2002

The United States Military Academy is faced with the situation whereby 700 cadets may
in a single subject
prepare computer programs
in class
one day and get their solutions in the form of a computer runoff at their next class attendance. If the programs had to be processed by conventional keypunch techniques the peak requirements for keypunching would be overwhelming. Keypunched cards with operator errors caused by misinterpreted coding sheets could not be returned to students for review and correction prior to the time the solutions are required in class. This situation has caused the Military Academy to investigate methods bypassing the keypunching operation. A number of special type mark-sense and Port-A-Punch cards have been used. Figure 1 shows a card used with SADSAC, a simplified academic design single address computer; Figure 2, a card for SASSY, a symbolic assembly program; Figure 3, a card for CADETRAN, a dialect of FORTRAN. (It contains the arithmetic statement X = 3.5 * A/(K**2 - C**2).) The CADETRAN/FORTRAN card is printed in four colors. Numbers (which require marking of a single position) are printed in black. Letters of the first third of the alphabet are printed in green, as is the 12-zone position which is identified A→I. Middle third letters of the alphabet are printed in red, as is the 11-zone position identified J→R. The final third of the alphabet is printed in blue as is the 0-zone position, and identified as S→Z. Commonly used symbols which would require 3 marks have been brought out to a separate left column where a single mark serves to identify them. Common but lengthy verbs such as FORMAT, DIMENSION and READ may also be represented by a single mark.
A back-end computer for data base management
Authors: Canaday R. H. , Harrison R. D. , Ivie E. L. , Ryder J. L. , Wehr L. A.
Published: July 2002

It is proposed that the data base management function be placed on a dedicated back-end computer which accepts commands (in a relatively high level language such as the CODASYL Data Base Task Group, April 1971 Report) from a host computer, accesses the data base on secondary storage, and returns results. The advantages of such a configuration are discussed. An experimental implementation, called the eXperimental Data Management System, XDMS, is described and certain conclusions about the back-end approach are drawn from this implementation.
On the synthesis of decision tables
Authors: Srinivasan B.
Published: July 2002

Synthesis of decision rules, each depicting a part of a decision process, is necessary in order to know the decision process in total perspective and to validate the consistency and the correctness of the decision logic. This paper proposes a method to synthesize a set of decision tables, each one of them representing a part of the decision logic, and thus serves as a tool for the system analyst in the system design phase.