bluuebunny/crossref_metadata_2025 huggingface dataset:
The GAMS classification scheme for mathematical and statistical software
Authors: Boisvert Ronald F. , Howe Sally E. , Kahaner David K.
Published: April 2007

An extensive tree-structured problem-oriented scheme for classifying mathematical and statistical software is presented. The scheme is a substantially modified version of a scheme proposed by Bolstad, which was based on the widely-used SHARE system. It is an attempt to reflect more accurately the current state of mathematical and statistical software. Our changes resulted from using the Bolstad scheme as the basis for the NBS Guide to Available Mathematical Software (GAMS), which provides NBS scientists information about subprograms in the IMSL, NAG, and PORT libraries, and in dozens of public-domain subprogram packages.
Cray 1 v. Cyber 205
Authors: Temperton Clive
Published: April 2007

During the past five years I have had the good fortune to be able to work on two of the world's fastest computers, the Cray-1 (at the European Centre for Medium Range Weather Forecasts) and the Cyber 205 (at the UK Meteorological Office). A comparison between the two machines is clearly of interest not only to potential users but also to a more general audience. In this article I will point out some of the differences between the two machines, and the impact these differences have on the way in which certain problems should be formulated and programmed.
Issues in license agreements for numerical program libraries
Authors: Brown W. S. , Fong K. W. , Ford B.
Published: April 2007

During the past decade, several organizations have developed high quality libraries of mathematical subroutines that are either portable or well supported on a variety of important computers. Although some progress has been made in persuading practitioners to use these libraries, it has become apparent that the licensing contracts and negotiations are a serious barrier to their acceptance. It is essential to have a contract to define the product and service being offered and the relationship between the producer and the customer. Yet, in more than a few cases, prospective customers have found it impossible to accept restrictions that the producers consider barely adequate to protect their most fundamental interests. In other cases, the bargaining may continue for months or even years before agreement is reached.
An "off-the-shelf" dynamic mesh capability
Authors: Corless R. M. , Simpson R. B.
Published: April 2007

In this note, we describe some experimental computations to examine embedding two point boundary value problem software in a time stepping procedure to solve one space variable dynamic problems. By using a general bvp solver with adaptive mesh selection in a simple, black box manner, we could expect to get a program package that could handle quite general system dynamics and boundary values and with a dynamic mesh capability for a relatively small development cost. This would, of course, be a trade-off of low development costs for high execution time costs and one of the main goals of our experiment has been to obtain some idea of the run time costs. We give here a brief overview of these computations, without references; details and references are available in University of Waterloo, Computer Science research report CS-82-32 "A Feasibility Study of the Use of COLSYS in the Solution of Systems of Partial Differential Equations"
Numerical experiments with SPARSPAK
Authors: Lewis John Gregg
Published: April 2007

The book COMPUTER SOLUTION OF LARGE SPARSE POSITIVE DEFINITE SYSTEMS, by Alan George and Joseph Liu, is both an excellent text on direct ordering methods and a thorough reference on the Waterloo Sparse Matrix Package SPARSPAK. Unfortunately their numerical experiments fail to make the case that the work was worthwhile. The rather small differences among the methods have left some readers with the impression that there really are no substantial reasons to go beyond banded methods. That is certainly not the authors' intent nor the correct conclusion, but it is easy to see how the readers were misled. The purpose of this note is to reopen the question, and perhaps kindle some debate which will uncover new evidence on the issue of choosing appropriate orderings.
Single-valued conversion of decimal numbers to rational fractions
Authors: Pyzalski R. , Vala M.
Published: April 2007

A single-valued conversion of decimal numbers to rational fractions has been formulated using a continued fraction expansion under the condition that the precision of the numbers to be converted is matched with the maximum expected denominator.
A proposal for an extended set of Fortran Basic Linear Algebra Subprograms
Authors: Dongarra Jack J. , Croz Jeremy Du , Hammarling Sven , Hanson Richard J.
Published: April 2007

This paper describes an extension to the set of Basic Linear Algebra Subprograms. The extensions proposed are targeted at matrix vector operations which should provide for more efficient and portable implementations of algorithms for high performance computers.
A proposed radix- and word-length-independent standard for floating-point arithmetic
Authors: Cody W. J. , Coonen J. T. , Gay D. M. , Hanson K. , Hough D. , Kahan W. , Karpinski R. , Palmer J. , Ris F. N. , Stevenson D.
Published: April 2007

The Microprocessor Standards Committee of the IEEE Computer Society sponsors two groups drafting proposed standard for floating-point arithmetic. The first, Task P754, reported Draft 10.0 of a Proposed Standard for Binary Floating-point Arithmetic out of committee in December. 1982. That document is now a de facto standard and is progressing slowly through the approval process within the IEEE Computer Society.
A note on estimating the error in Gaussian elimination without pivoting
Authors: Chu Eleanor , George Alan
Published: April 2007

This article deals with the problem of estimating the error in the computed solution to a system of equations when that solution is obtained by using Gaussian elimination without pivoting. The corresponding problem, where either partial or complete pivoting is used, has received considerable attention, and efficient and reliable methods have been developed. However, in the context of solving large sparse systems, it is often very attractive to apply Gaussian elimination without pivoting, even though it cannot be guaranteed a-priori that the computation is numerically stable. When this is done, it is important to be able to determine when serious numerical errors have occurred, and to be able to estimate the error in the computed solution. In this paper a method for achieving this goal is described. Results of a large number of numerical experiments suggest that the method is both inexpensive and reliable.
Mathematical software at KFA
Authors: Hake J. Fr.
Published: April 2007

Scientific computing at research centres does not only require fast computers and appropriate mathematical software. From the end-user's point of view there is also a need for a unified and flexible presentation of and access to the existing software tools. This paper deals with the strategy how mathematical software is incorporated into largescale computing at KFA Jülich.
The singular value decomposition in multivariate statistics
Authors: Hammarling Sven
Published: April 2007

To Gene Golub who has done so much to encourage and advance the use of stable numerical techniques in multivariate statistics.
Programming tools for linear algebra
Authors: Lipps H. , Erskine G. A.
Published: April 2007

Dongarra et al have recently proposed extensions to the subprogram package BLAS to improve the performance of more elaborate linear algebra codes such as LINPACK. (See [2] - [4]) We summarize here our experience with a similar project.
Three mysteries of Gaussian elimination
Authors: Trefethen Lloyd N.
Published: April 2007

If numerical analysts understand anything, surely it must be Gaussian elimination. This is the oldest and truest of numerical algorithms. To be precise, I am speaking of Gaussian elimination with partial pivoting, the universal method for solving a dense, unstructured
n X n
linear system of equations
Ax = b
on a serial computer. This algorithm has been so successful that to many of us, Gaussian elimination and
Ax = b
are more or less synonymous. The chapter headings in the book by Golub and Van Loan [3] are typical -- along with "Orthogonalization and Least Squares Methods," "The Symetric Eigenvalue Problem," and the rest, one finds "Gaussian Elimination," not "Linear Systems of Equations."
Design and implementation of a Fast Poisson solver for microcomputers
Authors: Chikhliwala E. D.
Published: April 2007

In this note we describe the design and implementation of a Fast Poisson solver for microcomputers [1]. A Double Fourier Transformation Algorithm [4] was used with Sinusoidal Transformations [2] for the different boundary conditions. Table 1 summarizes the classification of Sinusoidal Transformations according to different boundary conditions.
A mathematical software environment
Authors: Williams Donald L.
Published: April 2007

Several hundred scientists and engineers work at Amoco Production Company's Tulsa Research Center. Naturally, scientific computing is an important part of their research in petroleum exploration and production. General purpose mathematical and statistical software is often overlooked when it could be used in place of writing code. Our strategy for increasing the awareness and usage of existing software is through advertisement of software via a reusable software catalog, through regular inhouse presentations of a mathematical software seminar, and through the development of a Mathematical Software Environment, a collection of programs and procedures created to encourage the use of general purpose mathematical software.
Another factor of (10
31
-1)/9
Authors: Higginbotham T. F.
Published: April 2007

A second factor of (10
31
-1)/9 was found to be 6943319 with the use of an eight spoke wheel [1]. The spokes D(i) were 1, 7, 11, 13, 17, 19, 23, and 29. The possible factors 2, 3, and 5 were tested prior to starting the wheel. The constant multiplier was 30. The possible divisors were of the form30 *
K
+
D(i), K
= 0, 1, 2, 3,....The program was written in COBOL for the Honeywell DPS 8, running under CP-6. The picture clauses were selected such that 31-digit decimal arithmetic was used. Execution time was about forty-five minutes.
Test for (IN) equality, subtraction, proof of correctness
Authors: Dunham Charles B.
Published: April 2007

As normally implemented, (in)equality tests such as "a < b" can fail to execute correctly and thus algorithms that have been "proven" may fail.
Three proposed amendments to the draft proposed ANS FORTRAN Standard
Authors: Ford B. , Reid J. K. , Smith B. T.
Published: April 2007

In this note details are given of three additions to the draft proposed ANS FORTRAN Standard published in SIGPLAN NOTICES, March 1976. These amendments were proposed by the members of IFIP Working Group 2.5 on Numerical Software and submitted to the X3J3 committee in July, 1976. We hope that this note will encourage interested parties to send for copies of the full specifications, consider the proposals and then communicate their reactions to the IFIP WG 2.5 committee and to the X3J3 committee.The objective of the proposals is to extend Standard FORTRAN to enhance the portability, adaptibility, ease of use and reliability of FORTRAN Software, without substantial impact upon the spirit and philosophy of the current proposed standard.This note gives a brief description of the proposals and their background. Separate documents detail the line-by-line changes to the Standard. Copies may be obtained by writing to NAG Central Office, 13 Banbury Road, OXFORD or Dr. J. C. T. Pool, Applied Mathematics Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, Illinois 60439.
An experimental system for exploring applications of hypertext in workstation environments
Authors: Gawor Mary , Bauer Michael
Published: April 2007

Hypertext is a tool which allows machine supported references between pieces of text in a single underlying database. This article outlines the implementation of
xhype
, a prototype hypertext system developed as a vehicle for exploring different aspects of hypertext systems and for examining different uses for hypertext in workstation environments. The system has been implemented for Sun workstations using the X11 windowing system.
IMPRESS
Authors: Armer Mike
Published: April 2007

IMPRESS (Interdisciplinary Machine Processing for Research and Education in the Social Sciences) is an integrated set of computer programs and social science data sets designed to allow students and faculty who have very little computer expertise to analyze and manipulate social science data in a time-sharing environment. The user of IMPRESS need not know computer programming in order to access the 64 data sets currently on disc in the IMPRESS public library, nor is it necessary to prepare data decks or instruction cards. The user's only task is to type in simple English commands at his console and await the return of the tables, plots, and statistics he has requested. Indeed, even the most naive first-time user of IMPRESS can generally produce some sort of intelligent output within an hour or so of his introduction to the system. This interactive capability means that undergraduates can learn non-trivial social science data analysis at the freshman and sophomore level, and that both faculty and students can regularly do their own quantitative research, and incorporate that research in their courses.
Describing a social science data information system, networks and components
Authors: Peters Paul E.
Published: April 2007

The acquisition of data has taken its place with the acquisition of literature as a first-order information problem for social science practitioners, researchers, and students. The traditional mechanisms of information dissemination have been serial publications and professional meetings which provide linkages for social science practitioners and researchers, while monographs and textbooks serve the basic needs of students. Brittain (1), however, has suggested that social scientists are unique as scientists because they utilize large volumes of data often produced outside their immediate control. [1] The costs associated with social science data collection in the quantity required for reliable research have occasioned discussions related to the possibility of data resource dissemination. This dissemination leads to secondary or extended analysis', whereby one researcher applies data to problems not thematic to those researchers who collected the data and performed a 'primary analysis'.
Facilitating information access
Authors: Rowe Judith
Published: April 2007

During the last twenty years, social scientists involved with the establishment and administration of data archives have been making overtures to traditional libraries. But until recently, there has been almost no response. In 1957, York Lucci and Stein Rokkan proposed a "library center of survey research data." [1] In 1965, Ithiel de Sola-Pool argued cogently that "the storing of basic data... [is] a library function." [2] In 1967, Ralph Bisco addressed the question, "Why should university libraries undertake data services...?" [3] That same year, a report prepared for the National Academy of Sciences examined some of the factors which seemed to vitiate against a merger of data archives and traditional libraries. [4] In 1969, at the last conference of the Council of Social Science Data Archives, David Elesh, then director of Wisconsin's Social Science Data and Program Library Service, and Erwin Welsch, Wisconsin's Social Studies Librarian, addressed an audience composed of data archivists and librarians on "The Library of the Future." [5] In 1970, Jack Dennis, present director of the Data and Program Library Service, addressed a conference of librarians where he spoke of the need for "closer integration of the local archive into existing local university information services--particularly those provided by the traditional university library." [6] By 1971, when David Nasitir summarized the history of the data archive movement's attempts to establish a rapprochement with the traditional library [7], there was little positive activity to report. However, in commenting on a paper delivered by Constance Citro in 1968, which was concerned with the desire on the part of the Bureau of the Census to allow libraries to manage the summary tapes of the 1970 census [8], his words proved prophetic. Nasitir said, "This is the one area in which the data archive movement is converging with academic libraries....If the census tapes form the thin end of the wedge, a large number of sample survey data tapes now held in archives may follow." [9] The wedge is now in the door and the remainder of this discussion will look briefly at the evidence of its presence.
Social science computing curricula
Authors: Anderson Ronald E.
Published: April 2007

Several decades ago a new body of techniques sprouted from the field of mathematics. This new technology, which came to be called statistics, grew into an autonomous academic field despite confining pressures. Although the invention of computer techniques historically lagged behind statistics, its entry into the academic world is strikingly similar. Both fields face issues of disciplinary autonomy and both are undergoing similar struggles between applied and theoretical interests. One outcome of these tensions in statistics has been the establishment of separate programs for applied statistics. While we do not dare make rigid predictions for computer science, we would anticipate similar structures, e.g., applied computer science curricula, to emerge.
A computer generated bibliography
Authors: Gottlieb Allan , Bodoff Joan
Published: April 2007

The dominant use of computers in the social and behavioral sciences is for numeric calculations. For example, the statistical packages, SPSS, etc., have enjoyed widespread use and econometric models have often been implemented on computers, e.g. MIT's TROLL project.
On the sociology of computing
Authors: Sim Francis , Anderson Ronald E.
Published: April 2007

This work was supported in part by NSF Grant GZ-3431 for a College Faculty Workshop on Computer Science in Social and Behavioral Science Education at the University of Colorado, 1974.
University computing as a political process
Authors: Wiste Richard
Published: April 2007

The various activities engaged in by those involved in computing can be looked upon from a number of perspectives. A choice of psychological, economic, geographic, political, or other perspectives may be made either on largely heuristic grounds or on grounds more closely tied to serious argument concerning the proper conduct of the activity under discussion. The choice of perspective embodied in this paper was made largely on the latter grounds. The basic argument is that, for many purposes, computing should be looked upon as a political process. If it were looked upon in this way, many things might be done otherwise, and the changes would be decidedly for the better.
Evaluating the "friendliness" of a timesharing system
Authors: Borman Lorraine , Karr Rosemary
Published: April 2007

The decade of the Sixties served to introduce most university campuses to the computer; the Seventies brought the computer, via a terminal, into every facet of university life. Computing in the Eighties will cause every university and college to evaluate and reconsider its exploitation of modern computing equipment for education and research.
SOCK
Authors: Alba Richard D. , Gutmann Myron P.
Published: April 2007

The SOCK system is intended to provide a set of procedures for sociometric clique identification. The procedures in SOCK are based upon numerical clustering techniques which isolate highly interrelated subsets of individuals. Since clustering techniques do not generally work well when operating on simple dichotomous choice data, i.e., on adjacency matrices, these procedures involve the derivation of some matrix of pairwise social distance or proximity from the dichotomous choice data.
SOUPAC
Authors: Chouinard Paul
Published: April 2007

SOUPAC is a general purpose statistical package designed and implemented at the University of Illinois, Urbana-Champaign.
Considerations in selecting a terminal
Authors: Marks Gregory A.
Published: April 2007

The computer terminal marketplace is expanding and changing rapidly. Prices are dropping as a result of both technological factors and because of sales volume. An increasing variety of special features and capabilities are appearing. However, the selection process can be a confusing one. This article is intended to help anyone interested in terminals by setting forth the major trade-offs and considerations that may be relevant.
A computer applications course: 1970-1979
Authors: Sidel Philip
Published: April 2007

In Volume 2, No. 2 of this Bulletin (December 1970), I described the course I was conducting in Computer Applications for the Social Sciences. Now, over eight years later, I am still teaching that course. It is interesting to look at the changes in content and organization.
The computer age and the White Man's burden
Authors: Patterson Diana
Published: April 2007

The Computer Age is nearly upon us. That's when the ordinary worker and householder find that they have to use a computer regularly during the course of their day. Making the Computer Age a reality has been, and continues to be, another White Man's Burden. The White Man, in this case, is not necessarily white or male, but his burden is as real to him now as it was to the Victorian Englishman.
A contribution towards the measurement of user behavior
Authors: Wilke Helmut G.
Published: April 2007

Within the context of a university computing center, user and uses of SPSS (Statistical Package for the Social Sciences) have been investigated. Several methods of data collection are discussed and results are presented. Besides a general user survey and general accounting data, a statistical software logfile proved to be an elegant and powerful method to obtain information on the basis of individual runs.
Computers and politics in China
Authors: Gordon Andrew C.
Published: April 2007

Consider the following observations about the People's Republic of China:A team of "workers, peasants and soldiers" adhering in 1976 to the principle that "education must serve proletarian politics and be combined with productive labor," and working in a "simple workshop built through self-reliance" successfully developed a 1024-bit MOS random access memory chip for computers "with 5000 transistors on a chip one-fourth of the size of a fingernail."
A perspective on interactive survey analysis
Authors: Meyers Edmund D.
Published: April 2007

In this paper, interactive survey analysis is broadly conceived so that discussion is not limited simply to researchers fondling data files. The digital computer -- especially the time-shared type -- has potential for constructive use by researchers well beyond the process of analyzing survey data. Consideration is given to accomplished resources, projects under development, and capabilities which might be developed; so it is worth keeping an eye on what is fact and what is fantasy.
Automation of instrument design, coding, data entry, data cleaning, and codebook generation
Authors: Steinbrenner K.
Published: April 2007

In reviewing the survey process, it is clear that for all surveys certain common operations are involved which are independent of where the survey is done or who is in charge of it. To show how these various steps could become part of an integrated data processing system, I first want to describe each step separately, as it is accomplished normally. The description which follows is based on procedures executed at NORC, but similar steps are followed almost everywhere else. Certain terms might be unique to NORC, but their meaning should become clear from the context.
The social dynamics of instrumental computer use
Authors: Kling Rob , Scacchi Walter , Crabtree Phillip
Published: April 2007

During the last three decades, computing has far surpassed its early role as a laboratory device for scientific computation. Computers are presently used for a wide array of purposes. In most of its uses it is portrayed as a problem-solving tool and as a material or intellectual object. Despite continuing technical advances, computer use is still costly in its demands for attention and special skills by people (instrumental users) who try to use it to further their own work, whether they program or not. These problems occur because much computer use is inextricably embedded in a complex set of problematic social relationships between groups of service providers and consumers. In particular, serious and continual use of computing forces users to attend to issues associated with:1. The work setting of computer use;2. Understanding the capabilities of computing;3. The scope and rate of technical change;4. Insuring that data is accurate, complete, and timely;5. Control over computing resources;6. The overall time that attention to these social and technical issues require.The opportunities and problems of instrumental computer use vary when users utilize different technologies and different organizational arrangements for supporting them. However, as software and hardware developments progress, the social arrangements of computer use will increasingly dominate the attention of users.
L. P. Behavior - recursion example comments
Authors: Hart W. D.
Published: April 2007

These are comments on the recursion research results reported by C. A. Haverly in this issue of SIGMAP Bulletin. The particular figures used introduce a fascinatingly unco-operative model, with a split "useful answer" area.
An improved line search technique
Authors: Bell Bradley M.
Published: April 2007

A current version of the Davies, Swann and Campey algorithm is stated. An estimate of the error at each iteration is then derived. This estimate is used to show that the current version is inefficient in a certain sense. A modified algorithm is then defined, implemented, and tested. The results show that the error estimate is accurate and the new algorithm is faster.
Reducing computational effort in solving a hard integer program
Authors: Daniel R. C.
Published: April 2007

This note describes the actual steps taken by the author in attempting to get insight into the effective solution of a hard integer program. A reduction in CPU time of around 97% was eventually achieved, but the major purpose of the note is to reinforce the moral that a subtlety of approach is still necessary to solve economically even small discrete problems.
Behavior of recursion model - more studies
Authors: Haverly C. A.
Published: April 2007

In our continuing interest in the subject of the behavior of L. P. Models, I have hit upon a rather interesting Recursion Model. It was described in my previous article in the Sigmap Bulletin (1). This article describes further studies made on the model.
A nonlinear programming test problem
Authors: Himmelblau D. M.
Published: April 2007

Figure 1 is a flow diagram of the chemical process. The test problem was a hydrocarbon refrigeration process in which the feed stream (stream number 1 of Figure 1) is a vapor mixture of ethane, propane, and n-butane (subscripts e, p and b, respectively) at 200°F and 500 psia. The product stream (stream number 8 of Figure 1) is liquid at -20°F at some reduced pressure. The nonlinear objective function was the minimization of the cost of the work done by the recycle stream compressors. There were 34 bounded variables (both upper bound and lower bound) associated with the process, 12 linear equality constraints, 18 nonlinear equality constraints, and 3 linear inequality constraints (see PROBLEM). The generalized reduced gradient code of Abadie and Guigou reached the solution shown in Table 1 from the nonfeasible starting point shown in Table 2.
Recursion model behavior
Authors: Haverly C. A.
Published: April 2007

Studies on the behavior of an LP pooling model while being solved by Recursion have been reported in prior SIGMAP Bulletins (1), (2), (3) and (4). This article reports the results of some further studies on the same model.
Alternate optimal solutions
Authors: Haverly C. A.
Published: April 2007

The behavior of LP models is a topic in which I have had some interest in recent years. I speak of behavior of the model itself, as distinct from the behavior of the algorithm, the solution path or the accuracy of the model representation. I have submitted several papers on this topic before to the SIGMAP bulletin (1, 2, 3). In this paper I consider model behavior as reflected in alternate optimal solutions.
Recent and future developments in SPERRY UNIVAC's FMPS product
Authors: McCall Edward H.
Published: April 2007

This paper surveys recent (past eight years) and future developments in SPERRY UNIVAC's 1100 Series mathematical programming product, FMPS (FMPS is an acronym for Functional Mathematical Programming System). In addition, computational results are given for FMPS algorithm and I/O enhancements.
Data structures in honeywell's MPS/66
Authors: Despain Gerald
Published: April 2007

The methods used for data manipulation in Honeywell's MPS/66 are described. These methods are based on database ideas and hierarchial trees. Implications on data inputs, revisions, matrix generation, etc. are discussed.
The extended control language of MPSX/370; simple and advanced applications
Authors: Spielberg Kurt
Published: April 2007

Commercial linear programming (LP) systems are important efficient, general and robust. One can expect of them that they can cope rapidly with linear programs of very large size, even if these are not particularly well formulated. They can accept and solve models of wide diversity, and therefore permit the redesign and modification of problems which is characteristic of almost all practical operations research studies (in contrast to specialized algorithms and codes, which have the tendency to become useless when the problem changes unexpectedly). And finally, they have become remarkably sturdy in the face of poor data such as redundant or similar constraints, degeneracy and general numerical difficulty.
Mathematical programming systems, subsystems, and supersystems
Authors: Jenkin D. Alan
Published: April 2007

Mathematical programming systems are becoming more difficult to define due to increasingly powerful abilities to interface different systems. The evolution and characteristics of the systems are described in terms of various real-world applications and specific implementations. A projection of past trends in development is made for a description of future system characteristics.
Khachian's algorithm fact and fantasy
Authors: Fieldhouse Martin
Published: April 2007

Just a year ago in 1979 L. G. Khachian, a Russian, published an algorithm for solving linear programming problems. Khachian's algorithm has theoretical advantages over the algorithm published by G. B. Dantzig in 1947 which is known as the simplex method.
User control of large-scale programming models
Authors: Fuglestad Paul
Published: April 2007

Operational mathematical programming models can be quite complex, requiring considerable expertise in operations research, computer techniques, and data management. While it is true that many managers and public or corporate policy makers possess these requisite skills, many more decision-makers must rely on modelers to build, maintain, and interpret their management information systems. Either of these situations can be costly in terms of time and money.
2
Dealing with a modeling/processing group can represent lengthy turnaround; running a model himself will detract a manager from other duties.
Reasonableness tests for gradient-based function minimization algorithms
Authors: Brusch Richard G.
Published: April 2007

Many of the most effective function optimization algorithms require the gradient of the function to be optimized. In many cases of practical interest the gradient is not available in closed form and must be approximated numerically, finite differences being the most frequent approach. This note suggests a number of reasonableness tests which can be performed on the gradient vector to aid the user in identifying the erroneous problem formulations and poor problem scaling.
On MPS evaluation and gunslinging
Authors: Hirshfeld David S.
Published: April 2007

This note responds to two recent items in the SIGMAP Bulletin:•December '77: "Benchmark Test of MPSX/370 vs. MPSIII" by Patrick G. Falk•April '78: "User Evaluation of MPSX/370 - SHARE 49, Washington, D.C." August 22, 1977 by Patrick G. Falk and James J. TumbuschBoth deal with essentially the same set of data and test results.
EDP application mix selection using zero-one programming
Authors: Solomon Susan L.
Published: April 2007

The problem of selecting a data processing system and determining the set of applications to be performed by the chosen system is one which confronts more as well as smaller firms every year. The use of management science techniques in making these crucial decisions has been very limited. Some firms which can afford the relatively high cost of doing so have implemented simulation packages {10, 25} or written a custom simulation model to assist in the selection or modification of hardware and software systems. Occasionally, simulation is used to evaluate alternative data management schemes after the equipment has been chosen. In all such situations the application mix is taken as given. The firm which cannot or will not undertake such a heavy commitment of funds is left with traditional system evaluation aids such as benchmarks or subjective assessments. These methods are unrigourous and imprecise and, again, the application set is assumed fixed.
Program termination analysis in polynomial time
Authors: Ben-Amram Amir M. , Lee Chin Soon
Published: April 2007

Asize-change termination algorithmtakes as input abstract information about a program in the form ofsize-change graphsand uses it to determine whether any infinite computation would imply that some data decrease in size infinitely. Since such an infinite descent is presumed impossible, this proves program termination. The property of the graphs that implies program termination is called SCT. There are many examples of practical programs whose termination can be verified by creating size-change graphs and testing them for SCT.The size-change graph abstraction is useful because the graphs often carry sufficient information to deduce termination, and at the same time are simple enough to be analyzed automatically. However, there is a tradeoff between the completeness and efficiency of this analysis, and complete algorithms in the literature can easily be pushed to an exponential combinatorial search by certain patterns in the graph structures.We therefore propose a novel algorithm to detect common forms of parameter-descent behavior efficiently. Specifically, we target lexicographic descent, multiset descent, and min- and max-descent. Our algorithm makes it possible to verify practical instances of SCT while guarding against unwarranted combinatorial search. It has worst-case time complexity cubic in the input size, and its effectiveness is demonstrated empirically using a test suite of over 90 programs.
Compilability of propositional abduction
Authors: Liberatore Paolo , Schaerf Marco
Published: April 2007

Abduction is one of the most important forms of reasoning; it has been successfully applied to several practical problems, such as diagnosis. In this article we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) is often known before the rest of the problem. In this article, we show some complexity results about abduction when compilation is allowed.
Trace cache sampling filter
Authors: Behar Michael , Mendelson Avi , Kolodny Avinoam
Published: April 2007

A simple mechanism to increase the utilization of a small trace cache, and simultaneously reduce its power consumption, is presented in this article. The mechanism uses selective storage of traces (filtering) that is based on a new concept in computer architecture: random sampling. The sampling filter exploits the “hot/cold trace” principle, which divides the population of traces into two groups. The first group contains “hot traces” that are executed many times from the trace cache and contribute the majority of committed instructions. The second group contains “cold traces” that are rarely executed, but are responsible for the majority of writes to an unfiltered cache. The sampling filter selects traces without any prior knowledge of their quality. However, as most writes to the cache are of “cold traces” it statistically filters out those traces, reducing cache turnover and eventually leading to higher quality traces residing in the cache. In contrast with previously proposed filters, which perform bookkeeping for all traces in the program, the sampling filter can be implemented with minimal hardware. Results show that the sampling filter can increase the number of hits per build (utilization) by a factor of 38, reduce the miss rate by 20% and improve the performance-power efficiency by 15%. Further improvements can be obtained by extensions to the basic sampling filter: allowing “hot traces” to bypass the sampling filter, combining of sampling together with previously proposed filters, and changing the replacement policy in the trace cache. Those techniques combined with the sampling filter can reduce the miss rate of the trace cache by up to 40%. Although the effectiveness of the sampling filter is demonstrated for a trace cache, the sampling principle is applicable to other micro-architectural structures with similar access patterns.
The Web as a graph
Authors: Donato Debora , Laura Luigi , Leonardi Stefano , Millozzi Stefano
Published: April 2007

In this article we present an experimental study of the properties of webgraphs. We study a large crawl from 2001 of 200M pages and about 1.4 billion edges, made available by the WebBase project at Stanford, as well as several synthetic ones generated according to various models proposed recently. We investigate several topological properties of such graphs, including the number of bipartite cores and strongly connected components, the distribution of degrees and PageRank values and some correlations; we present a comparison study of the models against these measures.Our findings are that (i) the WebBase sample differs slightly from the (older) samples studied in the literature, and (ii) despite the fact that these models do not catch all of its properties, they do exhibit some peculiar behaviors not found, for example, in the models from classical random graph theory.Moreover we developed a software library able to generate and measure massive graphs in secondary memory; this library is publicy available under the GPL licence. We discuss its implementation and some computational issues related to secondary memory graph algorithms.
Defeating DDoS attacks by fixing the incentive chain
Authors: Huang Yun , Geng Xianjun , Whinston Andrew B.
Published: April 2007

Cooperative technological solutions for Distributed Denial-of-Service (DDoS) attacks are already available, yet organizations in the best position to implement them lack incentive to do so, and the victims of DDoS attacks cannot find effective methods to motivate them. In this article we discuss two components of the technological solutions to DDoS attacks: cooperative filtering and cooperative traffic smoothing by caching. We then analyze the broken incentive chain in each of these technological solutions. As a remedy, we propose usage-based pricing and Capacity Provision Networks, which enable victims to disseminate enough incentive along attack paths to stimulate cooperation against DDoS attacks.
Perl 6
Authors: Tang Audrey
Published: April 2007

Perl is a general-purpose language, known for its vast number of freely available libraries. The Perl 6 project was started to improve the language's support for multi-paradigmatic programming, while retaining compatibility with the existing code base. This talk discusses how Perl 6 attempts to reconcile various competing paradigms in the field of programming language design, such as static vs. dynamic typechecking, nominal vs. structural subtyping, prototype vs. class-based objects, and lazy vs. eager evaluation. Moreover, this talk also covers the design and development of Pugs, a self-hosting Perl 6 implementation bootstrapped from Haskell, targeting multiple runtime environments, including Perl 5, JavaScript and Parrot.
Semantics of static pointcuts in aspectJ
Authors: Avgustinov Pavel , Hajiyev Elnar , Ongkingco Neil , de Moor Oege , Sereni Damien , Tibble Julian , Verbaere Mathieu
Published: April 2007

In aspect-oriented programming, one can intercept events by writing patterns called
pointcuts
. The pointcut language of the most popular aspect-oriented programming language, AspectJ, allows the expression of highly complex properties of the static program structure.We present the first rigorous semantics of the AspectJ pointcut language, by translating static patterns into safe (
i.e.
range-restricted and stratified) Datalog queries. Safe Datalog is a logic language like Prolog, but it does not have data structures; consequently it has a straightforward least fixpoint semantics and all queries terminate.The translation from pointcuts to safe Datalog consists of a set of simple conditional rewrite rules, implemented using the Stratego system. The resulting queries are themselves executable with the CodeQuest system. We present experiments indicating that direct execution of our semantics is not prohibitively expensive.
A typed intermediate language for compiling multiple inheritance
Authors: Chen Juan
Published: April 2007

Type-preserving compilation can improve software reliability by generating code that can be verified independently of the compiler. Practical type preserving compilation does not exist for languages with multiple inheritance. This paper presents E
mi
, the first typed intermediate language to support practical compilation of a programming language with fully general multiple inheritance. The paper demonstrates the practicality of Emi by showing that E
mi
can be used to faithfully model standard implementation strategies of multiple inheritance for C++, the most widely-used programming language with general multiple inheritance.
Dynamic heap type inference for program understanding and debugging
Authors: Polishchuk Marina , Liblit Ben , Schulze Chloë W.
Published: April 2007

C programs can be difficult to debug due to lax type enforcement and low-level access to memory. We present a dynamic analysis for C that checks heap snapshots for consistency with program types. Our approach builds on ideas from physical subtyping and conservative garbage collection. We infer a program-defined type for each allocated storage location or identify "untypable" blocks that reveal heap corruption or type safety violations. The analysis exploits symbolic debug information if present, but requires no annotation or recompilation beyond a list of defined program types and allocated heap blocks. We have integrated our analysis into the GNU Debugger (gdb), and describe our initial experience using this tool with several small to medium-sized programs.
Compositional dynamic test generation
Authors: Godefroid Patrice
Published: April 2007

Dynamic test generation is a form of dynamic program analysis that attempts to compute test inputs to drive a program along a specific program path. Directed Automated Random Testing, or DART for short, blends dynamic test generation with model checking techniques with the goal of systematically executing all feasible program paths of a program while detecting various types of errors using run-time checking tools (like Purify, for instance). Unfortunately, systematically executing
all
feasible program paths does not scale to large, realistic programs.This paper addresses this major limitation and proposes to perform dynamic test generation
compositionally
, by adapting known techniques for interprocedural static analysis. Specifically, we introduce a new algorithm, dubbed
SMART
for
Systematic Modular Automated Random Testing
, that extends DART by testing functions in isolation, encoding test results as function summaries expressed using input preconditions and output postconditions, and then re-using those summaries when testing higher-level functions. We show that, for a fixed reasoning capability, our compositional approach to dynamic test generation (SMART) is both sound and complete compared to monolithic dynamic test generation (DART). In other words, SMART can perform dynamic test generation compositionally without any reduction in program path coverage. We also show that, given a bound on the maximum number of feasible paths in individual program functions, the number of program executions explored by SMART is linear in that bound, while the number of program executions explored by DART can be exponential in that bound. We present examples of C programs and preliminary experimental results that illustrate and validate empirically these properties.
A very modal model of a modern, major, general type system
Authors: Appel Andrew W. , Melliès Paul-André , Richards Christina D. , Vouillon Jérôme
Published: April 2007

We present a model of recursive and impredicatively quantified types with mutable references. We interpret in this model all of the type constructors needed for typed intermediate languages and typed assembly languages used for object-oriented and functional languages. We establish in this purely semantic fashion a soundness proof of the typing systems underlying these TILs and TALs---ensuring that every well-typed program is safe. The technique is generic, and applies to any small-step semantics including λ-calculus, labeled transition systems, and von Neumann machines. It is also simple, and reduces mainly to defining a Kripke semantics of the Gödel-Löb logic of provability. We have mechanically verified in Coq the soundness of our type system as applied to a von Neumann machine.
From implementation to theory in product synthesis
Authors: Batory Don
Published: April 2007

Future software development will rely on
product
synthesis, i.e., the synthesis of code and non-code artifacts for a target component or application. Prior work on feature-based product synthesis can be understood and generalized using elementary ideas from category theory. Doing so reveals (a) practical and previously unrecognized properties that product synthesis tools must satisfy, and (b) non-obvious generalizations of current techniques that will guide future research efforts in automated product development.
Lazy multivariate higher-order forward-mode AD
Authors: Pearlmutter Barak A. , Siskind Jeffrey Mark
Published: April 2007

A method is presented for computing all higher-order partial derivatives of a multivariate function R

n

→ R. This method works by evaluating the function under a nonstandard interpretation, lifting reals to multivariate power series. Multivariate power series, with potentially an infinite number of terms with nonzero coefficients, are represented using a lazy data structure constructed out of linear terms. A complete implementation of this method in
Scheme
is presented, along with a straightforward exposition, based on Taylor expansions, of the method's correctness.