bluuebunny/crossref_metadata_2025 huggingface dataset:
Traffic matrices
Authors: Soule Augustin , Lakhina Anukool , Taft Nina , Papagiannaki Konstantina , Salamatian Kave , Nucci Antonio , Crovella Mark , Diot Christophe
Published: January 2007

Traffic matrix estimation is well-studied, but in general has been treated simply as a statistical inference problem. In practice, however, network operators seeking traffic matrix information have a range of options available to them. Operators can measure traffic flows directly; they can perform partial flow measurement, and infer missing data using models; or they can perform no flow measurement and infer traffic matrices directly from link counts. The advent of practical flow measurement makes the study of these tradeoffs more important. In particular, an important question is whether judicious modeling, combined with partial flow measurement, can provide traffic matrix estimates that are signficantly better than previous methods at relatively low cost. In this paper we make a number of contributions toward answering this question. First, we provide a taxonomy of the kinds of models that may make use of partial flow measurement, based on the nature of the measurements used and the spatial, temporal, or spatio-temporal correlation exploited. We then evaluate estimation methods which use each kind of model. In the process we propose and evaluate new methods, and extensions to methods previously proposed. We show that, using such methods, small amounts of traffic flow measurements can have significant impacts on the accuracy of traffic matrix estimation, yielding results much better than previous approaches. We also show that different methods differ in their bias and variance properties, suggesting that different methods may be suited to different applications.
Predicting node availability in peer-to-peer networks
Authors: Mickens James W. , Noble Brian D.
Published: January 2007

Unlike the well-administered servers in traditional distributed systems, machines in peer-to-peer networks have widely varying levels of availability. Accurate modeling of node uptime is crucial for predicting per-machine resource burdens and selecting appropriate data replication strategies. In this research project, we improve upon the accuracy of previous peer-to-peer availability models, which are often too conservative to dynamically predict system availability at a fine-grained level. We test our predictors on availability traces from the PlanetLab distributed test bed and the Microsoft corporate network. Each trace has a distinct predictability profile, and we explain these differences by examining the fundamental uptime classes contained in each trace. We also show how availability-guided replica placement reduces the amount of object copying in a distributed data store.
Fair operation of multi-server and multi-queue systems
Authors: Raz David , Avi-Itzhak Benjamin , Levy Hanoch
Published: January 2007

This work aims at studying the fairness of multi-queue and multi-server queueing systems. We deal with the issues of queue-multiplicity, queue joining policy and queue jockeying and use a quantitative measure (RAQFM) to evaluate them. Our results yield the relative fairness of the mechanisms as a function of the system configuration and parameters. Practitioners can use these results to
quantitatively
account for system fairness and to weigh efficiency aspects versus fairness aspects in designing and controlling their queueing systems. In particular, we quantitatively demonstrate that: 1) Joining the shortest queue increases fairness, 2) A single "combined" queue system is more fair than "separate" (multi) queue system and 3) Jockeying from the head of a queue is more fair than jockeying from its tail.
Analysis of search and replication in unstructured peer-to-peer networks
Authors: Tewari Saurabh , Kleinrock Leonard
Published: January 2007

This paper investigates the effect of the number of file replicas on search performance in unstructured peer-to-peer networks. We observe that for a search network with a random graph topology where file replicas are uniformly distributed, the hop distance to a replica of a file is logarithmic in the number of replicas. Using this observation we show that flooding-based search is optimized when the number of replicas is proportional to the file request rates. This replica distribution is also optimal for download time and since flooding has logarithmically better search time than random walk under its optimal replica distribution, we investigate the query-processing load using this distribution.
Health aspects of wireless communication
Authors: Lin James C.
Published: January 2007

In a recently reported study, an increased risk of acoustic neuroma (also known as schwannoma) was found among persons in Sweden with 10 or more years of mobile-phone use [1]. There was no association with use less than 10 years, nor for other measures of use such as total hours of use or total number of calls made.
The holes problem in wireless sensor networks
Authors: Ahmed Nadeem , Kanhere Salil S. , Jha Sanjay
Published: January 2007

Several anomalies can occur in wireless sensor networks that impair their desired functionalities i.e., sensing and communication. Different kinds of holes can form in such networks creating geographically correlated problem areas such as coverage holes, routing holes, jamming holes, sink/black holes and worm holes, etc. We detail in this paper different types of holes, discuss their characteristics and study their effects on successful working of a sensor network. We present state-of-the-art in research for addressing the holes related problems in wireless sensor networks and discuss the relative strengths and short-comings of the proposed solutions for combating different kinds of holes. We conclude by highlighting future research directions.
An analytical model of operating system protocol processing including effects of multiprogramming
Authors: Danzig Peter B.
Published: January 2007

We model the limited buffer queueing process that occurs within the UNIX operating system's protocol processing layers. Our model accounts for the effects of user process multiprogramming and preemptive, priority scheduling of interrupt, operating system, and user tasks. After developing the model, we use it to predict message loss that occurs during local area network (LAN) multicast. Our service time model can be applied to window-and rate-based stream flow control.
Performance analysis of finite-buffered multistage interconnection networks with a general traffic pattern
Authors: Lin T. , Kleinrock L.
Published: January 2007

We present an analytical model for evaluating the performance of finite-buffered packet switching multistage interconnection networks using blocking switches under any general traffic pattern. Most of the previous research work has assumed unbuffered, single buffer or infinite buffer cases, and all of them assumed that every processing element had the same traffic pattern (either a uniform traffic pattern or a specific hot spot pattern). However, their models cannot be applied very generally. There is a need for an analytical model to evaluate the performance under more general conditions.We first present a description of a decomposition & iteration model which we propose for a specific hot spot pattern. This model is then extended to handle more general traffic patterns using a transformation method. For an even more general traffic condition where each processing element can have its own traffic pattern, we propose a superposition method to be used with the iteration model and the transformation method. We can extend the model to account for processing elements having different input rates by adding weighting factors in the analytical model.An approximation method is also proposed to refine the analytical model to account for the memory characteristic of a blocking switch which causes persistent blocking of packets contending for the same output ports. The analytical model is used to evaluate the uniform traffic pattern and a very general traffic pattern " EFOS". Comparison with simulation indicates that the analytical model is very accurate.
Performance measurement of a parallel Input/Output system for the Intel iPSC/2 Hypercube
Authors: French James C. , Pratt Terrence W. , Das Mriganka
Published: January 2007

The Intel Concurrent File System (CFS) for the iPSC/2 hypercube is one of the first production file systems to utilize the declustering of large files across numbers of disks to improve I/O performance. The CFS also makes use of dedicated I/O nodes, operating asynchronously, which provide file caching and prefetching. Processing of I/O requests is distributed between the compute node that initiates the request and the I/O nodes that service the request. The effects of the various design decisions in the Intel CFS are difficult to determine without measurements of an actual system. We present performance measurements of the CFS for a hypercube with 32 compute nodes and four I/0 nodes (four disks). Measurement of read/write rates for one compute node to one I/O node, one compute node to multiple I/O nodes, and multiple compute nodes to multiple I/O nodes form the basis for the study. Additional measurements show the effects of different buffer sizes, caching, prefetching, and file preallocation on system performance.
Performance of a disk array protype
Authors: Chervenak Ann L. , Katz Randy H.
Published: January 2007

The RAID group at U.C. Berkeley recently built a prototype disk array. This paper examines the performance limits of each component of the array usiug SCSI bus traces, Sprite operating system traces and user programs.The array performs successfully for a workload of small, random I/O operations, achieving 275 I/Os per second on 14 disks before the Sun4/280 host becomes CPU-limited. The prototype is less successful in delivering high throughput for large, sequential operations. Memory system contention on the Sun4/280 host limits throughput to 2.3 MBytes/sec under the Sprite Operating System. Throughput is also limited by the bandwidth supported by the VME backplane, disk controller and disks, and overheads associated with the SCSI protocol.We conclude that merely using a powerful host CPU and many disks will not provide the full bandwidth possible from disk arrays. Host memory bandwidth and throughput of disk controllers are equally important. In addition, operating systems should avoid unnecessary copy and cache flush operations that can saturate the host memory system.
An experiment on measuring application performance over the Internet
Authors: Pu Calton , Korz Frederick , Lehman Robert C.
Published: January 2007

The use of wide area networks (WANs) such as the Internet is growing at a tremendous rate.Such networks hold great promise for new types of distributed applications, which will be widely distributed, highly replicated, intensely interactive, and adaptive to many types of network conditions. Developing such applications will require a solid understanding of the performance and availability characteristics of WANs as they evolve. The ability to measure the effect of these conditions will, for example, be important for large-volume applications such as digital libraries, and for near-real-time applications such as collaborative research and teleconferencing.
Conjectural permutation decoding of some AG codes
Authors: Joyner David
Published: January 2007

We study the action of a finite group on the Riemann-Roch space of certain divisors on a specific hyperelliptic curve
X
defined over a finite field with "large" automorphism group
G
. If
D
and
E
=
P
l
+ ... +

P
n

are
G
-equivariant divisors on
X
(

P
i

∈
X
(
F
)) then
G
acts on associated AG code
C
=
C
(
D,E
) by permuting coordinates. This note discusses the permutation decoding of these AG codes. The main "results" are conjectures regarding the complexity of the permutation decoding of these hyperelliptic codes. The open source GAP error-correcting codes package GUAVA is used to compute examples.
SCRATCHPAD
Authors: Jenks R. D.
Published: January 2007

The following SCRATCHPAD solution of Problem #2 was run on a 1280K virtual machine under CP/CMS time sharing system on a System/360 model 67. The conversation below is a modification of a program originally written by Yngve Sundblad, August 1972. The program uses symmetrised formulae, saves certain intermediate results, but does not eliminate numerical factors in denominators.
TRIGMAN
Authors: Jeffreys W. H.
Published: January 2007

The TRIGMAN system, manipulates Poisson Series (trignometric series with polynomial coefficients). It consists of a set of FORTRAN preprocessor written in SNOBOL and a set of FORTRAN subroutine for elementary symbolic operations. The TRIGMAN source language resembles FORTRAN but with additional declarations. Programs are translated into legal FORTRAN then compiled.
An idea for comparing data structures
Authors: Fitch John , Norman Arthur
Published: January 2007

This short note describes an idea we had one coffee time, after reading Richard Fateman's thesis. In that document a number of comparative figures are given for various algebra systems calculating the f and g series, to order 10, Next to the entry for CAMAL, which incidently has the time wrong by a factor of five, he has a note to the effect that CAMAL was a packed representation of polynomials, resulting in a low number of pointers.
SAC-1 solution of problem #7
Authors: Collins G. E. , Musser D. R. , Rothstein M.
Published: January 2007

This note reports on various aspects of our experience in using the SAC-1 system to solve Problem #7, submitted by S. C. Johnson and R. L. Graham, [1]. In solving the problem, several separate SAC-1 main programs were written for the various parts of the problem. These separate programs could, in principle, have been combined into a single main program. The SAC-1 solution involved the use of seven of the ten currently released SAC-1 subsystems. With reference to Loos' bibliography, [2], the seven subsystems used were CO-12, CO-13, CO-14, CO-17, CO-15, CO-16 and CO-19; CO-18, CO-31 and CO-32 were not needed.
The automatic construction of pure recurrence relations
Authors: Verbaeten P.
Published: January 2007

A method is presented for the construction of pure recurrence relations for functions related to generalized hyper-geometric functions. It is an improvement of a technique by Fasenmeyer, and is suitable for automatic computer programming. Our method has an easy geometrical interpretation and also gives a constructive proof for the existence of a pure recurrence relation.
Implications of symbolic computation for the teaching of mathematics
Authors: Wang Paul S.
Published: January 2007

The experience gained in teaching an experimental computer calculus course using the symbolic manipulation system MACSYMA is described. Interesting course material is presented to show how symbolic computation on computer can facilitate the teaching and learning of calculus. Some other college mathematics topics that could benefit from symbolic systems are indicated. The advantages and difficulties of such an approach are discussed.
A theoretical basis for the reduction of polynomials to canonical forms
Authors: Buchberger B.
Published: January 2007

We define a certain type of bases of polynomial ideals whose usefulness stems from the fact that a number of computability problems in the theory of polynomial ideals (e.g. the problem of constructing canonical forms for polynomials) is reducible to the construction of bases of this type. We prove a characterization theorem for these bases which immediately leads to an effective method for their construction.
Automatic simplification for the absolute-value function and its relatives
Authors: Stoutemyer David R.
Published: January 2007

Computer symbolic mathematics has made impressive progress for the automatic simplification of rational expressions, algebraic expressions, and elementary transcendental expressions. However, existing computer-algebra systems tend to provide little or no simplification for the absolute-value function or for its relatives such as the signum, unit ramp, unit step, max, min, modulo, and Dirac delta functions. Although these functions lack certain desireable properties that are helpful for canonical simplification, there are opportunities for some
ad hoc
simplification. Moreover, a perusal of most mathematics, engineering, and scientific journals or texts reveals that these functions are too prevalent to be ignored.This article describes specific simplification rules implemented in a program that supplements the built-in rules for the MACSYMA ABS and SIGNUM functions.
Real root isolation for algebraic polynomials
Authors: Rump Siegfried M.
Published: January 2007

Several algorithms are known to separate the real zeros of a polynomial. In his thesis Heindel [He70] showed, that the computing time of his algorithm using Sturm sequences is polynomially bounded in the length of the coefficients. The polynomials are assumed to have integral coefficients. In his Diplomarbeit [Lü76] Ludicke gave a modified Sturm algorithm for real algebraic polynomials with a polynomially bounded, but very high computing time. He described and analyzed the algorithm, but did not implement it. In the present paper we extend the Collins/Loos - algorithm [CL76] from integral to real algebraic coefficients and gain empirical computing times.
The use of "LET" statements in producing short comprehensible outputs
Authors: Shtokhamer R.
Published: January 2007

It is shown that an algebraic implementation of "LET" statements may be useful in producing comprehensible outputs. The suggested algorithm is based on solving large set of linear equations over a field.
SIAM 1978 national meeting
Authors: Wang Paul S.
Published: January 2007

There are four invited speakers in the SAM Sessions of the SIAM 1978 National Meeting held on May 24-26 at the University of Wisconsin at Madison. Reprinted here by permission are the abstracts as appeared in the Proceedings published by SIAM. Abstracts of contributed papers have been included in the May issue of this bulletin.
Is a linked list the best storage structure for an algebra system?
Authors: Moenck Robert
Published: January 2007

Virtually all algebraic manipulation systems are very large programs which can only be run on the largest computers, and even then press the limits of the machines resources [1]. I see this as the principal reason for the lack of popularity of algebraic manipulation; namely for many potential users the costs involved in running these programs do not outweigh their benefits. The motivation for this note is to stimulate discussion about the design of algebra systems, with a view to making them more economically viable.
Towards a REDUCE solution to SIGSAM problem 7
Authors: Norman Arthur
Published: January 2007

Problem 7 (1) involves the generation and factorization of a certain 40th degree polynomial. This note relates my progress towards solving the problem using REDUCE: at present the programs involved are not as tidy as those displayed (for instance) in the MACSYMA or SCRATCHPAD solutions (2, 3), and the computing times still leave scope for improvement. The results are nevertheless there, and the extensions to REDUCE that I have made in the process of obtaining them give a clear demonstration of the amount of mechanism called into play by 'modern' algebra such as factorization. The solution of problem 7 splits naturally into three parts. The first of these calculates a pair of modest polynomials P and Q. This does not give REDUCE any trouble at all.
Abstracts
Authors: Wang Paul S.
Published: January 2007

Abstracts of papers to appear in the August 1979 issue of the SlAM Journal of Computing based on papers from the SlAM 1978 Spring Meeting held May 24-26, 1978 in Madison, Wisconsin:
A solution to problem #4
Authors: Griesmer James H. , Jenks Richard D.
Published: January 2007

The following SCRATCHPAD conversation for carrying out the Lie Transform computation represents a slight modification of one written by Dr. David Barton, when he was a summer visitor during 1972 at the Watson Research Center.
A solution of problem #3 using CAMAL
Authors: Fitch John
Published: January 2007

This short note is a response from CAMAL to a paper on REDUCE and MACSYMA [2], in which it was suggested that one should compare different algorithms on each system. Here CAMAL is used on a PDPIO to calculate the functions U
rs
(r+s≤4) by Fitch's repeated approximation algorithm [1] and C
rs
(r+s≤4) by Hall's method 2 [4], both solutions of SIGSAM problem 3 [3]. These figures can be compared with a similar comparison for REDUCE [2].
A p-adic division with remainder algorithm
Authors: Yun David Y. Y.
Published: January 2007

A new algorithm for division with remainder of univariate and multivariate polynomials over the integers is reported. This division algorithm relies on a p-adic construction which is closely related to the Hensel-type constructions used for polynomial factorization and greatest common divisor computations. It furnishes a new and systematic way of looking at the classical problem of division (with or without remainder). Due to the sparseness-preserving property of p-adic constructions, it appears useful as an alternative division algorithm in suitable cases when the polynomials are sparse. Detailed discussion and a more complete computing time analysis will be deferred until a later time as the work progresses further. An hope, in the meantime, is to attract comments and criticism on the algorithm and its significance.
Solutions to problem 8
Authors: Norman A. C.
Published: January 2007

In Problem 8 Fitch asks for solutions to a two-term recurrence formula. Only part of the full solution is needed, and the problem reduces to expanding a fairly complex function as a power series in one of its variables. Expressed in this way the problem is a direct application for the new SCRATCHPAD power series package (described elsewhere in this issue). The SCRATCHPAD program required is just that shown as Figure 1. Working through the zero order terms in the expansions shows that r will take the value sqrt(4q
2
) and so to simplify further working a line r=2q occurs immediately after the line defining r in general: this extra statement is present solely to make sure that the answer is not found unsimplified in terms of sqrt(4q
2
). Running on an IBM 370/168 in 1536Kbytes and using this program, SCRATCHPAD gets as far as the 8
th
term: timings and garbage collection counts are shown in Table 1. To show how the same algorithm can be used on other algebra system the problem was coded for an experimental assertional algebra system with a SCRATCHPAD-like input language. The program, reproduced as Figure 2, was gotten by hand simulating the SCRATCHPAD power series pre-processor. As can be seen, the program is fairly messy: it took quite a few trial runs and access to a set of expected answers to get the signs and temporary variables right! This program was run on the Cambridge University IBM 370/165 in the maximum partition allowed (400Kbytes) and got up to order 7 taking times shown in Table 2. As a final experiment the above algorithm was transcribed into CAMAL. The general system (H) was used, and arrays were used to store the power series coefficients. The program involved was even more unreadable than Figure 2, being slightly over 100 lines long, and is not given here. CAMAL was run on the 370/165, again in 400Kbytes: Table 3 give the relevant timing information.
Special purpose differentiation algorithms
Authors: van Hulzen J. A.
Published: January 2007

The structure of SIGSAM Problem #8, [1], motivated the development of algorithms to determine an arbitrary, say r-th, derivative with respect to t of a function f(t)
α
, where [EQUATION]
ALTRAN solution to problem #8
Authors: Hall A. D.
Published: January 2007

In SIGSAM Problem #8 [1], we are interested in the power series expansion of H
n
(t) defined by the recurrence relation:[EQUATION]
APL.NET encryption HOWTO
Authors: Kutinsky Vladimir
Published: January 2007

The article outlines the key points of building a Dyalog APL interface to the GNU Privacy Guard (GnuPG), a tool for cryptographic privacy and authentication. The main purpose of the interface is to use the GnuPG's functionality to encrypt data and create digital signatures directly from APL programs. The article briefly describes .NET classes that form the core of the interface and provide effective means to manage processes running on a computer. It also contains a number of examples demonstrating usage of the interface and the underlying ideas.
How we got to APL/1130
Authors: Breed Larry
Published: January 2007

APL/1130 was implemented overnight in the autumn of 1967, but it took years of effort to make that possible. In 1965, Ken Iverson's group in Yorktown was wrestling with the transition from Iverson Notation, a notation suited for blackboards and printed pages, to a machine-executable programming environment. Iverson had already developed a Selectric typeball and was writing a high-school math textbook. By autumn 1965, Larry Breed and Stanford grad student Philip Abrams had written the first implementation in 7090 Fortran (with batch execution). Eugene McDonnell was looking for applications to run on TSM, his project's experimental time-sharing system on a virtual-memory 7090. With his help, Breed ported the Fortran code, added I/O routines for the 1050 terminals, called the result IVSYS; and Iverson Notation went interactive.
Testing word-sized numbers for primality
Authors: Norman A. C.
Published: January 2007

Modular based algorithms, such as those used to compute GCDs, generally require a supply of word-sized primes. Such primes can, of course, be provided statically: it is easy to precompute and store a list of a dozen or so suitable numbers. It nevertheless seems attractive to generate them randomly, for instance by considering a sequence of random numbers until one of them is found to be prime. This strategy leads to a consideration of the cost of testing if a number is composite. This cost clearly depends on the typical size of numbers being used. For use with the arithmetic package I have, it is convenient to use a modulus in the range 2**23 to 2**24, and so the remarks and timings given here are relevant to that range.
Random oscillations arising in the MACSYMA implementation of Khachian-type algorithms in linear programming
Authors: Rajaram Navaratna S.
Published: January 2007

Anderson and Wang in [1] ran a series of experiments on MACSYMA to test the practicality of the now widely publicized Khachian algorithm for deciding the consistency of a system of linear inequalities. They found the Khachian algorithm to be highly impractical even for very small-sized problems which, in turn, led them to construct a modified algorithm which proved to be a substantial improvement over the original one. In this paper, results of a statistical analysis of data furnished by these experiments are presented. In particular, attention is focussed on the parameter α which in a sense measures, at each step, the saving in using the Anderson-Wang modified algorithm. An intriguing discovery is the fact that α
i
is a random time series which fluctuates between -1 and 0 before approaching zero as the procedure terminates.Also, it appears that much progress has to be made before such algorithms can be of use in practical problems.
Integration in finite terms
Authors: Kasper Toni
Published: January 2007

The search for elementary antiderivatives leads from classical analysis through modern algebra to contemporary research in computer algorithms.
Factorization of univariate polynomials
Authors: Mignotte Maurice
Published: January 2007

In order to obtain information about the average cost of the current algorithms to factorize univariate integral polynomials, we study the statistical behaviour of several natural functions on univariate polynomials over finite fields.
MODLISP
Authors: Davenport James H. , Jenks Richard D.
Published: January 2007

This paper discusses the design and implementation of MODLISP, a LISP-like language enhanced with the idea of MODes. This extension permits, but does not require, the user to declare the types of various variables, and to compile functions with the arguments declared to be of a particular type. It is possible to declare several functions of the same name, with arguments of different type (e.g. PLUS could be declared for Integer arguments, or Rational, or Real, or even Polynomial arguments) and the system will apply the correct function for the types of the arguments.
An application of reduce to industrial mechanics
Authors: Bordoni Luciana , Colagrossi Attilio
Published: January 2007

A REDUCE implementation of a method to obtain dynamical equations of motion for large mechanical systems is presented. These equations of motion are obtained by the Lagrange dynamical equations.
Lattices and factorization of polynomials
Authors: Lenstra A. K.
Published: January 2007

A new algorithm to factorize univariate polynomials over an algebraic number field has been implemented in Algol-68 on a CDC-Cyber 170-750 computer. The algebraic number field is given as the field of rational numbers adjoined by a root of a prescribed minimal polynomial. Unlike other algorithms [1,2] the efficiency of our so-called lattice algorithm does not depend on the irreducibility of the minimal polynomial modulo some prime. The factorization of the polynomial to be factored is constructed from the factorization of that polynomial over a finite field determined by a prime p and an irreducible factor of the minimal polynomial modulo p. The algorithm is based on a theorem on integral lattices and a theorem giving a lower bound for the length of a shortest-length polynomial having modulo p
k
a non-trivial common divisor with the minimal polynomial. These theorems also enable us to formulate a new algorithm for factoring polynomials over the integers. A technical report describing the algorithms will soon be available from the Mathematisch Centrum, Amsterdam.
Saving space in coset enumeration
Authors: Atkinson M. D.
Published: January 2007

Possibly the most frequently used algorithm in computational group theory is the Todd-Coxeter process for enumerating the cosets of a subgroup of a finitely presented group. In all implementations the power of this algorithm is limited much more by its storage requirements than by its execution time. This note outlines a technique which can often be used to economise on storage at the expense of an increased execution time. Before giving details it will be helpful to review some background.
On the parallel Risch algorithm (III)
Authors: Davenport James H.
Published: January 2007

In this note, we look at the extension to the parallel Risch algorithm (see, e.g., the papers by Norman & Moore [1977], Norman & Davenport [1979], ffitch [1981] or Davenport [1982] for a description of the basic algorithm) which represents trigonometric functions in terms of tangents, rather than instead of complex exponentials.
An algorithm for avoiding complex numbers in rational function integration
Authors: Renbao Zhong
Published: January 2007

Given a proper rational function A(x)/B(x) where A(x) and B(x) both are in R[x] with gcd(A(x), B(x))= 1, B(x) monic and deg(A(x)) < deg(B(x)), from the Hermite algorithm for rational function integration in [3], we obtain[EQUATION]where S(x) is a rational function which is called the rational part of the integral of A(x)/B(x) in eq. (1), B*(x) is the greatest square-free factor of B(x), and T(x) is in R[x] with deg(T(x)) < deg(B*(x)). The integral of T(x)/B*(x) is called the transcendental part of the integral of A(x)/B(x) in eq. (1).
The conversion of Hensel codes to their rational equivalents
Authors: Miola Alfonso M.
Published: January 2007

The problem of rational arithmetic has been studied recently by many authors. For instance we can mention the work of Horn [1978] and of Matula and Kornerup [1979].
A comparison of the Vaxima and Reduce factorization packages
Authors: Norman Arthur C. , Wang Paul S.
Published: January 2007

During 1979 the programmed version of the multivariate factorization algorithm described in [6] stabilized and replaced the old factoring algorithm in Macsyma as the standard factorizer. It has thus graduated from being a program written as part of a research project into being a tool that anyone with a copy of Macsyma may rely on. In 1981, a factoring package [4] was being prepared for distribution as a module in a forthcoming release of Reduce. During September 1982 the two authors were able to make some direct comparisons between their codes by running both factorizers on the same set of examples on the same computer at the same time. This note reports on the comparative timings so obtained.
On Coates algorithm
Authors: Berry T. G.
Published: January 2007

This paper relates the behaviour of Coates algorithm for the construction of rational functions on an algebraic curve to the algebro-geometric structure of the input. This enables us to answer a question of Davenport and provides a frame work in which Coates's algorithm may be compared with other algorithms for the same purpose.
Some comments on the modular approach to Gröbner-bases
Authors: Ebert G. L.
Published: January 2007

The problem of finding a modular algorithm for constructing Gröbner-bases is of interest to many computer algebraists. In particular, given a prime p and a set of (multivariate) polynomials with integer coefficients, it has been queried if the number of basis polynomials in a minimal normed Gröbner-basis for the polynomial ideal generated mod p has to be less than or equal to the corresponding number for the polynomial ideal generated over the rationals. In this paper we answer this question and related questions concerning the modular approach to Gröbner-bases, illustrating with several interesting examples, and we propose a criterion for determining "luckiness" of primes in the binomial case.
Solution of a general system of equations
Authors: Gonnet Gaston H. , Char Bruce W. , Geddes Keith O.
Published: January 2007

The following problem is intended to test the ability of a general solver of system of equations. Both systems are real examples that occur in the process of proving that there is no better iteration formula for finding the inverse of a number (
x
= 1/
a
) than[EQUATION]with at most two multiplications.
Congruent numbers
Authors: Zimmer H. G.
Published: January 2007

Since nowadays electronic high speed computers of various sizes and types are commonly used at schools of all levels it appears to be in order to propose some appropriate mathematical problems which can be approached by means of a computer. For students this way of attacking such problems is certainly a valuable experience and should become an essential part of their scientific education.
The future of symbolic computation
Authors: Huet Gérard
Published: January 2007

This note is a response to B. Buchberger call for Eurocal'85. It argues that the current scope of symbolic computation is a very active branch of computer science, whose extremes are classical algorithm theory on one hand, and proof theory on the other hand. The main paradigm of the domain is that algorithms, programming languages as well as mathematical proofs are all mathematical formulae subject to computer treatment.
A new generation of symbolic and algebraic computation systems
Authors: de Trias Regina Llopis
Published: January 2007

When we think of the future, it comes to our mind the new generation of computer systems that will become a reality. The Fifth Generation of Computer Systems is the central object goal of Japan' s ICOT project and is now being also considered as an object by other research and development worldknown projects. We believe that it is in the context of these Personal Inference Machines and Knowledge and Information Processing Systems that we have to view the future of Symbolic and Algebraic Computation.
Logic and algebraic computation
Authors: Bibel Wolfgang
Published: January 2007

Logic and algebra definitely derive from a common tradition of human thought which may be traced back deeply into the history of mathematics and philosophy. Leibniz and Boole are outstanding representatives in this tradition, that is in the more recent part of it. Today, we are familiar with the fact that algebraic theories may be treated in a logical setting and, conversely, logic may be introduced in a purely algebraic way.
An antitranslator of the RLISP language
Authors: Kryukov A. P.
Published: January 2007

The present paper is devoted to consideration of the preparation and realization of the RECONSTRUCTOR program intended for translation of texts from the LISP language into the REDUCE system language. Examples of the program's operation are presented.
Report on a national computer algebra workshop in Leipzig
Authors: Lassner W.
Published: January 2007

A national "Workshop on Computer Algebra, Systems and Applications" took place from September 10-12, 1984 at the Center of Theoretical Sciences (Naturwissenschaftlich-Theoretisches Zentrum --- NTZ) of the Karl-Marx-University (KMU) in Leipzig. The intention of this Center founded as cooperative institution, in which mathematicians, physicists, chemists, computer scientists, and also biologists participate, is, first, to stimulate and enforce the interdisciplinary research activities of theorists in these fields; second, to serve better national and international contacts; and third, to become a scientific school for students and young scientists interested in actual research fields at the border lines between the above sciences. Since computer algebra (symbolic and algebraic computation) lies in the intersection of physics, mathematics and computer science, the NTZ supports all activities in this field.
Interactive REDUCE
Authors: Kryukov A. P. , Rodinov A. Ya.
Published: January 2007

This paper deals with some distinctive characteristics of the REDUCE-2 computer algebra system operating in interactive mode. A brief description of a new version of the system with extended interactive capabilities is presented.
Support vector machines classification with a very large-scale taxonomy
Authors: Liu Tie-Yan , Yang Yiming , Wan Hao , Zeng Hua-Jun , Chen Zheng , Ma Wei-Ying
Published: January 2007

Very large-scale classification taxonomies typically have hundreds of thousands of categories, deep hierarchies, and skewed category distribution over documents. However, it is still an open question whether the state-of-the-art technologies in automated text categorization can scale to (and perform well on) such large taxonomies. In this paper, we report the first evaluation of Support Vector Machines (SVMs) in web-page classification over the full taxonomy of the Yahoo! categories. Our accomplishments include: 1) a data analysis on the Yahoo! taxonomy; 2) the development of a scalable system for large-scale text categorization; 3) theoretical analysis and experimental evaluation of SVMs in hierarchical and non-hierarchical settings for classification; 4) an investigation of threshold tuning algorithms with respect to time complexity and their effect on the classification accuracy of SVMs. We found that, in terms of scalability, the hierarchical use of SVMs is efficient enough for very large-scale classification; however, in terms of effectiveness, the performance of SVMs over the Yahoo! Directory is still far from satisfactory, which indicates that more substantial investigation is needed.
The algorithm description language ALDES (report)
Authors: Loos Rüdiger G. K.
Published: January 2007

ALDES is a formalization of the method to describe algorithms used in Knuth's books. The largest documentation of algebraic algorithms, Collins' SAC system for Computer Algebra, is written in this language. In contrast to PASCAL it provides automatic storage deallocation. Compared to LISP equal emphasis was placed on efficiency of arithmetic, list processing, and array handling. To allow the programmer full control of efficiency all mechanisms of the system are accessible to him. Currently ALDES is available as a preprocessor to ANSI Fortran, using no additional primitives.
Extended abstract of "a new approach to the symbolic factorization of multivariate polynomials"
Authors: Claybrook Billy G.
Published: January 2007

A heuristic factorization scheme that uses learning and other heuristic programming techniques to improve the efficiency of determining the symbolic factorization of multivariate polynomials with integer coefficients and an arbitrary number of variables and terms is described. This factorization scheme is implemented in the learning program POLYFACT and is applied only to multivariate polynomials. The factorization scheme cannot be considered to be a completely general factorization algorithm for there are some instances where the scheme can fail to factor a reducible polynomial. The practical utility of this scheme lies in trying to employ some of the heuristic techniques in an algorithm such as Wang's to reduce the combinatorial searching that must be done to obtain the truefactors of a multivariate polynomial over the integers. Wang's algorithm uses a bottom-up approach for determining the truefactors; whereas, the heuristic scheme in POLYFACT uses a top-down approach.
Some data conversions for managing the internal and output form of formac constants
Authors: Hanson James N. , Russo Phillip
Published: January 2007

Three PL/I functions for managing Formac constants have been throughly tested and documented. These functions are: FLT&CHR for converting double precision floating point numbers to rational form as a PL/I character strings, TRUNCATE for truncating the numerator and denominator of a Formac rational constant to prescribed length, and EXT&FLT for constructing a PL/I character string containing an arbitrary length (precision) floating point equivalent of a Formac rational constant.
The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem
Authors: Moses Joel
Published: January 2007

A problem common to many powerful programming languages arises when one has to determine what values to assign to free variables in functions. Different implementational approaches which attempt to solve the problem are considered. The discussion concentrates on LISP implementations and points out why most current LISP systems are not as general as the original LISP 1.5 system. Readers not familiar with LISP should be able to read this paper without difficulty since we have tried to couch the argument in ALGOL-like terms as much as possible.
Practical formula manipulation for theoretical chemistry
Authors: Schnupp Dr. Peter
Published: January 2007

It is not always easy to give a paper on the applications of certain computing techniques to a highly specialized branch of science. On the other hand, theoretical chemistry is already one of the biggest "customers" of numerical computing in science and offers a wide potential of nonnumerical problems to be solved as well. Being an independent software house eager to gain practical experience in this rather new field of computing, we were very glad that wie could start on some real-world scientific problems rather than implementing yet another formula manipulation system of doubtful practical use. The purpose of this paper is to present a rough overview of theoretical chemistry and the kind of formula manipulation the practical worker encounters in this field of science.
Symbolic mathematical computation in a Ph.D. Computer Science program
Authors: Caviness B. F. , Collins G. E.
Published: January 2007

Considering how many fools can calculate, it is surprising that it should be thought either a difficult or a tedious task for any other fool to learn how to master the same tricks....Being myself a remarkably stupid fellow,...[I] now beg to present to my fellow fools the parts that are not hard. Master these throughly and the rest will follow. What one fool can do, another can.
Weighted coloring based channel assignment for WLANs
Authors: Mishra Arunesh , Banerjee Suman , Arbaugh William
Published: January 2007

We propose techniques to improve the usage of wireless spectrum in the context of wireless local area networks (WLANs) using new channel assignment methods among interfering Access Points (APs). We identify new ways of channel re-use that are based on realistic interference scenarios in WLAN environments. We formulate a weighted variant of the graph coloring problem that takes into account realistic channel interference observed in wireless environments, as well as the impact of such interference on wireless users. We prove that the weighted graph coloring problem is NP-hard and propose scalable distributed algorithms that achieve significantly better performance than existing techniques for channel assignment. We evaluate our algorithms through extensive simulations and experiments over an in-building wireless testbed.
Secure universal mobility for wireless Internet
Authors: Dutta Ashutosh , Zhang Tao , Madhani Sunil , Taniuchi Kenichi , Fujimoto Kensaku , Katsube Yasuhiro , Ohba Yoshihiro , Schulzrinne Henning
Published: January 2007

The advent of the mobile wireless Internet has created the need for seamless and secure communication over heterogeneous access networks such as IEEE 802,11, WCDMA, cdma2000, and GPRS. An enterprise user desires to be reachable while outside one's enterprise networks and requires minimum interruption while ensuring that the signaling and data traffic is not compromised during one's movement within the enterprise and between enterprise and external networks. We describe the design, implementation and performance of a Secure Universal Mobility (SUM) architecture. It uses standard protocols, such as SIP and Mobile IP, to support mobility and uses standard virtual private network (VPN) technologies (e.g., IPsec) to support security (authentication and encryption.) It uses pre-processing and make-before-break handoff techniques to achieve seamless mobility across heterogeneous radio systems. It separates the handlings of initial mobility management and user application signaling messages from user application traffic so that VPNs can be established only when needed, thus reducing the interruptions to users.
Reputation-based Wi-Fi deployment
Authors: Salem Naouel Ben , Hubaux Jean-Pierre , Jakobsson Markus
Published: January 2007

Wi-Fi networks have a very strong potential: They are easy to deploy, they use unlicensed frequencies and they provide internet connectivity that is several times faster than by cable modem. However, two major problems still need to be solved: the lack of a seamless roaming scheme and the variable quality of service experienced by the users. The reputation-based solution presented in this paper solves both problems: It allows a mobile node to connect to a foreign Wireless Internet Service Provider (WISP) in a secure way while preserving its anonymity and it encourages the WISPs to provide the users with good QoS. We analyze the robustness of our solution against various attacks and we prove by means of simulations that our reputation model indeed encourages the WISPs to behave correctly. We also propose a simple mechanism that allows the WISPs to predict the QoS they are able to offer to the (mobile) clients.