| CS-2002-43 | ||||
|---|---|---|---|---|
| Title | Optimal Spaced Seeds for Finding Homologous Coding Regions | |||
| Authors | Brona Brejova and Daniel G. Brown | |||
| Abstract |
We
study
the
problem
of
computing
optimal
spaced
seeds
for
identifying
homologous
coding
DNA
sequences
in
large
genomic
data
sets.
We
develop
two
models
of
DNA
sequence
alignment
in
coding
regions,
and
using
data
sets
from
human/Drosophila
and
human/mouse
comparisons,
we
compute
optimal
spaced
seeds
using
a
dynamic
programming
algorithm.
The
seeds
we
identify
are
more
sensitive
by
far
at
identifying
homologous
regions
than
the
seeds
from
BLAST
or
from
PatternHunter,
and
also
significantly
improve
on
the
sensitivity
of
WABA,
which
also
uses
a
simple
spaced
seed.
In particular, in human/Drosophila comparisons, we offer an 82% improvement in false negatives over BLAST and a 33% improvement over WABA. Our results offer the hope of improved gene finding due to fewer missed exons in DNA/DNA comparison, and more effective homology search in general. | |||
| Date | October 2002 | |||
| Report | Optimal Spaced Seeds for Finding Homologous Coding Regions (PS) | Optimal Spaced Seeds for Finding Homologous Coding Regions (PDF) | ||
| CS-2002-42 | ||||
|---|---|---|---|---|
| Title | A High-level Specification Language for Structured Document Transformation | |||
| Authors | X. Tang and F. W. Tompa | |||
| Abstract | The purpose of this paper is to introduce and study the problem of automatic transformation of structured documents. We consider collections of documents where the instances in each collection share a common structure in the sense that they can all be characterized by grammar rules such as found in a context-free grammar (CFG) or forest-regular grammar (FRG). We extend the notation to a single XML (or SGML) document with accompanying DTD (document type definition) to say that it is structured. As long as documents do not conform to a single universal standard, the data transformation between them remains a problem. Thus in the absence of a universal tag set and schema, structured document transformation is important for XML to serve as the data interchange format for the web. Recently, W3C proposed XSLT (Extensible Stylesheet Language Transformations) as a transformation language for XML data. This language has considerable computation power. However, it requires detailed and tedious programming to accomplish complex structure transformations. As alternatives, SDT (Syntax Directed Translation) and its extended form TT (Tree Transformation) grammar are widely used to specify transformations of source code in various programming languages, and they have been proposed as specification languages for structured document transformation. These languages are descriptive but have limited expressive power, which makes them unable to specify complex structure transformations. In this paper, we propose an approach based on syntax tree templates. We show that our language is both descriptive and expressive. We also provide algorithms to convert our specification to XSLT for executing the transformation. Based on the algorithms, we present a prototype implementation. | |||
| Date | October 2002 | |||
| Report | A High-level Specification Language for Structured Document Transformation (PDF) | |||
| CS-2002-41 | ||||
|---|---|---|---|---|
| Title | Wei Wei Zheng and Keith O. Geddes | |||
| Authors | Exploiting Fast Hardware Floating Point in High Precision Computation | |||
| Abstract | We present an iterative refinement method bases on a linear Newton iteration for solving a particular group of high precision computation problems. Our method generates an initial solution at hardware floating point precision using a traditional method and then repeatedly refines this solution to higher precision, exploiting hardware floating point computation in each iteration. This is in contrast to direct solution of the high precision problem completely in software floating point. Theoretical coast analysis, as well as experimental evidence, shows a significant reduction in computational cost is achieved by the iterative refinement method on this group of problems. | |||
| Date | December 2002 | |||
| Report | Exploiting Fast Hardware Floating Point in High Precision Computation (PS) | Exploiting Fast Hardware Floating Point in High Precision Computation (PDF) | ||
| CS-2002-40 | ||||
|---|---|---|---|---|
| Title | An XQuery Canonical Form and its Translation to Extended Relational Algebra | |||
| Authors | H. Zhang and F. W. Tompa | |||
| Abstract | As XML becomes more widespread as a standard representation for data, XML-based query languages and their evaluations are increasingly important. For this purpose, several XML based query languages have been proposed, including W3C's XQuery. In this paper, we define a query canonical form which provides a conceptually uniform vision of path expressions, element constructors and FLWR expressions in XQuery. The power of this canonical form is shown by identifying an important subset of XQuery that can be translated to this canonical form. Moreover, this canonical form nicely separates different aspects of an XML query, i.e., structure, navigation, and condition. This property makes it easy to be extended, and a possible extension of the canonical form is presented. Having this canonical form, we present an algorithm to translate from it into an extended relational algebra that includes operators defined for the structured text datatype, and we prove its correctness. This algorithm can be used as the basis of a sound translation from XQuery to SQL, and the starting point for query optimization, which is required for XML to be supported by relational database technology.l | |||
| Date | October 2002 | |||
| Report | An XQuery Canonical Form and its Translation to Extended Relational Algebra (PDF) | |||
| CS-2002-39 | ||||
|---|---|---|---|---|
| Title | XBench - A Family of Benchmarks for XML DBMSs | |||
| Authors | Benjamin Bin Yao, M. Tamer Ozsu and John Keenleyside | |||
| Abstract |
XML
is
beginning
to
be
extensively
used
in
various
application
domains,
and
as
a
result,
large
amounts
of
XML
documents
are
being
generated.
Researchers
in
both
industry
and
academia
have
proposed
a
number
of
approaches
to
efficiently
store,
manipulate,
and
retrieve
XML
documents.
The
individual
performance
characteristics
of
these
approaches
as
well
as
the
relative
performance
of
various
systems
is
an
ongoing
concern.
The range of XML application and the XML data that they manage are quite varied and no one database schema and workload can properly capture this variety. We propose a family of XML benchmarks, collectively call XBench, to measure and evaluate the performance of different approaches to deal with the management of XML documents. The family is defined according to a classification of applications, and each class has its own database and workload. We discuss the general requirements for an XML DBMS benchmark, followed by a detailed explanation of the XBench, including the methodology of database generation, the workload, and the setup of test environment. A brief discussion of other existing XML benchmarks and comparison among them will be given as well. | |||
| Comments | 163 pgs | |||
| Report | XBench - A Family of Benchmarks for XML DBMSs (PS) | XBench - A Family of Benchmarks for XML DBMSs (PDF) | ||
| CS-2002-37 | ||||
|---|---|---|---|---|
| Title | Fraction-free Row Reduction of Matrices of Ore Polynomials | |||
| Authors | Berhard Beckermann, Howard Cheng and George Labahn | |||
| Abstract |
In
this
paper
we
give
formulas
for
performing
row
reduction
of
a
matrix
of
Ore
polynomials
in
a
fraction-free
way.
The
reductions
can
be
used
for
finding
the
rank
and
left
nullspace
of
such
matrices.
When specialized to matrices of skew polynomials our reduction can be used for computing a weak Popov form of such matrices and for computing a GCRD and an LCLM of skew polynomials or matrices of skew polynomials. The algorithm is suitable for computation in exact arithmetic domains where the growth of coefficients in intermediate computations is a central concern. This coefficient growth is controlled by using fraction-free methods. The known factor can be predicted and removed efficiently. | |||
| Date | November 2002 | |||
| Report | Fraction-free Row Reduction of Matrices of Ore Polynomials (PS) | Fraction-free Row Reduction of Matrices of Ore Polynomials (PDF) | ||
| CS-2002-36 | ||||
|---|---|---|---|---|
| Title | Optimizing Correlated Path Queries in XML Languages | |||
| Authors | Ning Zhang and Tamer Ozsu | |||
| Abstract | Path expressions are ubiquitous in XML processing languages such as XPath, XQuery, and XSLT. Expressions in these languages typically include multiple path expressions, some of them correlated. Existing approaches evaluate these path expressions one-at-a-time and miss the optimization opportunities that may be gained by exploiting the correlations among them. In this paper, we address the evaluation and optimization of correlatedpath expressions. In particular, we propose two types of optimization techniques: integrating correlated path expressions into a single pattern graph, and rewriting the pattern graph according to a set of rewriting rules. The first optimization technique allows the query optimizer to choose an execution plan that is impossible by using the existing approaches. The second optimization technique rewrites pattern graphs at a logical leveland produce a set of equivalent pattern graphs from which a physical optimizer can choose given an appropriate cost function. Under certain conditions that we identify, the graph pattern matching-based executionapproach that we propose may be more efficient than the join-based approaches. | |||
| Date | November 2002 | |||
| Report | Optimizing Correlated Path Queries in XML Languages (PDF) | |||
| CS-2002-35 | ||||
|---|---|---|---|---|
| Title | A User Interest Model for Web Page Navigation | |||
| Authors | Sule Gunduz and M. Tamer Ozsu | |||
| Abstract | Making recommendation requires predicting what is of interest to a user at a specific time. Even the same user may have different desires at different times. This paper concentrates on the discovery and modelling of the user's aggregate interest in a session. This approach relies on the premise that the visiting time of a page is an indicator of the user's interest in that page. The proportion of times spent in a set of pages requested by the user within a single session forms the aggregate interest of that user in that session. We first partition user sessions into clusters such that only sessions which represent similar aggregate interest of users are placed in the same cluster. We employ a according to similar amount of time in similar pages. In particular, we cluster sessions by learning a mixture of Poisson models using Expectation Maximization algorithm. The resulting clusters are then used to recommend pages to a user that are most likely contain the information which is of interest to that user at that time. Although the approach does not use the sequential patterns of transactions, experimental evaluation shows that the approach is quite effective in capturing a web user's access pattern. The model has an advantage over previous proposals in terms of speed and memory usage. | |||
| Date | October 2002 | |||
| Report | A User Interest Model for Web Page Navigation (PS) | A User Interest Model for Web Page Navigation (PDF) | ||
| CS-2002-33 | ||||
|---|---|---|---|---|
| Title | Reducing the Dimensionality of Plant Spectral Databases | |||
| Authors | Ian Bell and Gladimir Baranoski | |||
| Abstract |
This
study
investigates
the
application
of
Principal
Components
Analysis
(PCA)
in
the
storage
and
reconstruction
of
plant
spectral
data.
A
new
Piecewise
PCA
approach
(PPCA),
which
takes
into
account
the
biological
factors
that
affect
the
interaction
of
solar
radiation
with
plants,
is
also
proposed.
These
techniques
are
examined
through
experiments
involving
the
reconstruction
of
reflectance
and
transmittance
curves
for
herbaceous
and
and
woody
specimens.
The
spectral
data
used
in
these
experiments
was
obtained
from
the
LOPEX
(Leaf
Optical
Properties
Experiment)
database.
The
reconstructions
were
performed
aiming
at
a
root
mean
square
error
(rmse)
lower
than
1%.
The
results
of
these
experiments
indicate
that
PCA
can
effectively
reduce
the
dimensionality
of
plant
spectral
databases
from
the
visible
to
the
infrared
regions
of
the
light
spectrum,
and
that
the
PPCA
approach
can
further
maximize
the
accuracy/cost
ratio
of
the
storage
and
reconstruction
of
plant
spectral
reflectance
and
transmittance
data.
| |||
| Report | Reducing the Dimensionality of Plant Spectral Databases (PS) | |||
| CS-2002-32 | ||||
|---|---|---|---|---|
| Title | Symbolic Summation in Maple | |||
| Authors | S.A. Abramov, K.O. Geddes, J.J. Carette, H.Q. Le | |||
| Abstract |
We
describe
the
design
and
implementation
of
the Maple toolbox SumTools, a package for computing closed forms of indefinite and definite sums. | |||
| Date | December 2002 | |||
| Report | Symbolic Summation in Maple (PS) | Symbolic Summation in Maple (PDF) | ||
| CS-2002-31 | ||||
|---|---|---|---|---|
| Title | Lazy Database Replication with Freshness Guarantees | |||
| Authors | K. Daudjee and K. Salem. | |||
| Abstract | Lazy replication is a popular technique for improving the performance and availability of database systems. Although there are concurrency control techniques which guarantee serializability in lazy replication systems, these techniques do not provide freshness guarantees. Since transactions may see stale data, they may be serialized in an order different from the one in which they were submitted. Strong serializ- ability avoids such problems, but it is very costly to imple- ment. In this paper, we propose a generalized form of strong serializability that is suitable for use with lazy replication. It has many of the advantages of strong serializability, but can be implemented more efficiently. We show how gener- alized strong serializability can be implemented in a lazy replication system, and we present the results of a simula- tion study that quantifies the strengths and limitations of the approach. | |||
| Date | November 2002 | |||
| Report | Lazy Database Replication with Freshness Guarantees (PDF) | |||
| CS-2002-30 | ||||
|---|---|---|---|---|
| Title | Streaming MPEG-4 Audio-Visual Objects with Quality Adaptation | |||
| Authors | Toufik Ahmed (1),(2), Youssef Iraqi (1), Raouf Boutaba (1) and Ahmed Mehaoua (2) | |||
| Abstract | This paper presents an Object-based Quality Adaptation Mechanism (OQAM) for streaming unicast MPEG-4 Audio-Visual content over the Internet. This mechanism dynamically adds and drops MPEG-4 Audio-Visual Objects (AVOs) by using a TCP-Friendly Rate Control (TFRC) mechanism. TFRC adjusts the number of AVOs streamed to meet the need for rapid change in transmission rate caused by network congestion and the need for stable perceptual audio-visual quality. This end-to-end quality adaptation is combined with a Diffserv marking scheme to guarantee AVOs prioritization within the network. Performance evaluation shows that the quality of the received video adapts gracefully to network state and to heterogeneous clients capabilities. | |||
| Date | August 2002 | |||
| Report | Streaming MPEG-4 Audio-Visual Objects with Quality Adaptation (PDF) | |||
| CS-2002-29 | ||||
|---|---|---|---|---|
| Title |
An
Efficient
Algorithmic
Approach for the Estimation of the Red Edge Position of Plant Leaf Reflectance | |||
| Authors | Gladimir V. G. Baranoski and Jon G. Rokne | |||
| Abstract | The point of maximum slope on the reflectance spectrum of vegetation between red and near-infrared wavelengths< is known as the red edge position (REP). The REP is stronglycorrelated with foliar chlorophyll content, and hence, it provides a very sensitive indicator for a variety of environmental factors such as vegetation stress, drought and senescence. Due to its importance for the application of inversion procedures, a number of techniques have been developed for determining the REP for foliar spectral reflectance. In this paper a new approach is proposed. It allows an unsupervised estimation of the REP. The accuracy of the new approach is evaluated by comparing REP estimates with values derived from measured spectral data for woody and herbaceous pecies. | |||
| Date | August 2002 | |||
| Report | An Efficient Algorithmic Approach for the Estimation of the Red Edge Position of Plant Leaf Reflectance (PDF) |
Compressed
PostScript: An Efficient Algorithmic Approach for the Estimation of the Red Edge Position of Plant Leaf Reflectance (GZIP) | ||
| CS-2002-26 | ||||
|---|---|---|---|---|
| Title | A Phase Velocity Analysis of Multigrid Methods for Hyperbolic Equations | |||
| Authors | Justin W.L. Wan, Tony F. Chan | |||
| Abstract |
In this paper, we study the effects of coarse grid correction (CGC) on multigrid convergence for hyperbolic problems in one and two dimensions. We approach this from the perspective of phase velocity, which allows us to exploit the hyperbolic nature of the underlying PDE. In particular, we consider three combination of coarse grid operators and coarse grid solution approaches: (1) Runge-Kutta smoothing CGC, direct discretization, (2) exact coarse grid solve, direct discretization, and (3) Galerkin CGC. For all these approaches, we show that the convergence behavior of multigrid can be precisely described by the phase velocity analysis of the coarse grid correction matrix, and we verify our results by numerical examples in one and two dimensions. | |||
| Date | July 2002 | |||
| Comments | Conference presentation: Householder Symposium XV | |||
| Report | A Phase Velocity Analysis of Multigrid Methods for Hyperbolic Equations (PS) | A Phase Velocity Analysis of Multigrid Methods for Hyperbolic Equations (PDF) | ||
| CS-2002-25 | ||||
|---|---|---|---|---|
| Title | Closed form solutions of linear odes having doubly periodic coefficients | |||
| Authors | Reinhold Burger, George Labahn, Mark van Hoeij | |||
| Abstract | We consider the problem of finding closed form solutions of linear differential equations having doubly periodic coefficients. We give a decision procedure for determining if such equations have doubly periodic solutions and study algorithms for solving such a decision procedure. In addition, in the case of a second order equation we show how to find the general solution to such an ode. | |||
| Date | July 2002 | |||
| Report | Closed form solutions of linear odes having doubly periodic coefficients (PDF) |
Compressed
PostScript: Closed form solutions of linear odes having doubly periodic coefficients (GZIP) | ||
| CS-2002-23 | ||||
|---|---|---|---|---|
| Title | On the Equivalence Between Prony's and Ben-Or's/Tiwari's Methods | |||
| Authors | Mark Giesbrecht, George Labahn, Wen-shin Lee. | |||
| Abstract |
We
show
the
equivalence
between
the
exact
\BenTi
algorithm
and
numerical
Prony's
method.
Taking
advantage
of
the
recent
results
in
both
exact
and
numerical
approaches,
we
present
new
algorithms
and
outline
possible
developments. Key words:Prony's method, sparse polynomial interpolation, early termination, Ben-Or/Tiwari algorithm, exponential functions. | |||
| Date | July 2002 | |||
| Report | On the Equivalence Between Prony's and Ben-Or's/Tiwari's Methods (PS) | On the Equivalence Between Prony's and Ben-Or's/Tiwari's Methods (PDF) | ||
| CS-2002-22 | ||||
|---|---|---|---|---|
| Title | SNAP User's Guide | |||
| Authors | Claude-Pierre Jeannerod, George Labahn, | |||
| Abstract | In this paper we describe the SNAP (Symbolic-Numeric Algorithms for Polynomials) package for computing with polynomials having inexact coefficients. This package is a first attempt to provide the standard functionalities for inexact polynomials that exist for exact polynomials, including the taking of quotients and remainders, determining if two polynomials are relatively prime and finding greatest common divisors (GCDs). The package is included in the coming release of the MAPLE computer algebra system. | |||
| Report | SNAP User's Guide (PDF) |
Compressed
PostScript: SNAP User's Guide (GZIP) | ||
| CS-2002-21 | ||||
|---|---|---|---|---|
| Title | Virtual Goniophotometric Measurements Protocol | |||
| Authors | Aravind Krishnaswamy, Gladimir V. G. Baranoski and Jon G. Rokne | |||
| Abstract | Many scattering models have been proposed in the graphics literature. Few of them, however, have been evaluated through comparisons with real measured data. As the demand for plausible and predictable scattering models increases, more effort is focused on performing such comparisons, which require the use of measurement devices. Once the accuracy of a given model is determined, data can be extracted from this model in several dimensions. In this paper we examine the formulation of virtual goniophotometric devices used to evaluate and extract data from scattering models. We discuss implementation issues which affect the reliability of the readings provided by these devices. Our discussion of these issues is supported by experiments whose results are also presented in this paper. | |||
| Report | Virtual Goniophotometric Measurements Protocol (PDF) | Virtual Goniophotometric Measurements Protocol (PS)t | ||
| CS-2002-17 | ||||
|---|---|---|---|---|
| Title | State of the Art in the Realistic Simulation of Plant Leaf Venation Systems | |||
| Authors | Julia Taylor-Hell and Gladimir Baranoski | |||
| Abstract | In order to create a realistic portrayal of plant leaves in computer graphics, the veins on these leaves must be represented. In the computer graphics industry, an artist may draw a branching vein structure as a texture and paste it onto the leaf model. Because natural scenes are so frequently represented, it would be useful to devise an automatic and predictable technique for simulating leaf venation systems and embedding them to the leaf's geometric model. This technical report examines this problem and reviews the state of the art in the simulation of venation systems. | |||
| Date | April 2002 | |||
| Report | State of the Art in the Realistic Simulation of Plant Leaf Venation Systems (PDF) |
Compressed
PostScript: State of the Art in the Realistic Simulation of Plant Leaf Venation Systems (GZIP) | ||
| CS-2002-16 | ||||
|---|---|---|---|---|
| Title | Simulating the Dynamics of the Dancing Lights | |||
| Authors | Gladimir Baranoski, Justin Wan, Jon Rokne, Ian Bell | |||
| Abstract | The auroral displays, known as the Aurora Borealis and Aurora Australis, are geomagnetic phenomena of impressive visual characteristics and remarkable scientific value. Auroras present a complex behavior that arises from interactions between plasma (hot, ionized gases composed of ions, electrons and neutral atoms) and Earth's electromagnetic fields. In this paper we present a physically-based model to perform 3D visual simulations of auroral dynamics. This model takes into account the physical parameters and processes directly associated with plasma flow. The set of partial differential equations associated with these processes is solved using a practical multigrid algorithm, which can also be applied in the simulation of natural phenomena such as gas, smoke or water flow. In order to illustrate the applicability of our model we provide animation sequences rendered using a distributed forward mapping approach. | |||
| Date | May 2002 | |||
| Report | Simulating the Dynamics of the Dancing Lights (PDF) |
Compressed
PostScript: Simulating the Dynamics of the Dancing Lights (GZIP) | ||
| CS-2002-14 | ||||
|---|---|---|---|---|
| Title | A Formal Analysis of the Will-Retire Correctness Statement | |||
| Authors | Nancy A. Day, Mark D. Aagaard and Meng Lou | |||
| Abstract | We relate two microprocessor correctness statements and show that they are equivalent. The first correctness statement in question uses synchronization at retirement over a series of steps of the implementation and external equality as the required correspondence between states. The second correctness statement is the classic single-step commuting diagram with external equality as the match. We prove that if any microprocessor implementation and specification are shown to satisfy one of these correctness statements, they also satisfy the other correctness statement. This technical report is a continuation of Technical Report 2002-11 and includes little introductory material. | |||
| Date | March 2002 | |||
| Report | A Formal Analysis of the Will-Retire Correctness Statement (PS)t | A Formal Analysis of the Will-Retire Correctness Statement (PDF) | ||
| CS-2002-13 | ||||
|---|---|---|---|---|
| Title | A Collapsing Method for Efficient Recovery of Best Supported Edges in Phylogenetic Trees | |||
| Authors | Mike Hu, Paul Kearney | |||
| Abstract | We present a novel algorithm, HyperCleaning* for effectively inferring phylogenetic trees. The method is based on the quartet method paradigm and is guaranteed to recover the best supported edges of the underlying phylogeny based on the witness quartet set. This is performed efficiently using a collapsing mechanism that employs memory/time tradeoff to ensure no loss of information. This enables HyperCleaning* to solve the relaxed version of the Maximum-Quartet-Consistency problem feasibly, thus providing a valuable tool for inferring phylogenies using quartet based analysis. | |||
| Date | March 2002 | |||
| Report | A Collapsing Method for Efficient Recovery of Best Supported Edges in Phylogenetic Trees (PDF) |
Compressed
PostScript: A Collapsing Method for Efficient Recovery of Best Supported Edges in Phylogenetic Trees (GZIP) | ||
| CS-2002-11 | ||||
|---|---|---|---|---|
| Title | A Mechanized Theory of Microprocessor Correctness Statements | |||
| Authors | Nancy A. Day, Mark. D. Aagaard, and Meng Lou | |||
| Abstract | Microprocessor verification has become increasingly challenging with the use of optimizations such as out-of-order execution. Because of the complexity of the implementations, a wide variety of microprocessor correctness statements have been proposed and used in verification efforts. In this work, we have mechanized a previously proposed framework for classifying these correctness statements. We have verified the relationships between the different points in the framework, and developed a characterization of the commonly used flushing abstraction function. The relationships between points in the framework are general theorems that provide "verification highways" to connect different correctness statements and provide reusable verification strategies. We have used these highways to determine the precise relationships between top-level correctness statements used in verification efforts. | |||
| Date | February 2002 | |||
| Report | A Mechanized Theory of Microprocessor Correctness Statements (PDF) |
Compressed
PostScript: A Mechanized Theory of Microprocessor Correctness Statements (PS.Z) | ||
| CS-2002-10 | ||||
|---|---|---|---|---|
| Title | High-Order Lifting | |||
| Authors | Arne Storjohann | |||
| Abstract | The well-known technique of adic-lifting for linear-system solution is studied. Some new methods are developed and applied to get algorithms for the following problems over the ring of univariate polynomials with coefficients from a field: rational system solving, integrality certification and determinant/ Smith-form computation. All algorithms are Las Vegas probabilistic. | |||
| Date | # issued in February | |||
| Comments | Submitted to: ISSAC '02 | |||
| Report | High-Order Lifting (PDF) |
Compressed
PostScript: High-Order Lifting (PS.Z) | ||
| CS-2002-07 | ||||
|---|---|---|---|---|
| Title | Factoring Zero-dimensional Ideals of Linear Partial Differential Operators | |||
| Authors | Ziming Li, Fritz Schwarz, Serguei P Tsarev | |||
| Abstract |
This
paper
presents
an
algorithm
for
factoring
a
zero-dimensional
left
ideal
in
the
ring
generated
by
two
derivation
operators
over
the
field
of
bivariate
rational
functions,
i.e.,
factoring
a
linear
homogeneous
partial
differential
system
whose
coefficients
are
rational
functions,
and
whose
solution
space
is
finite-dimensional
over
the
field
of
constants.
The
algorithm
computes
all
the
zero-dimensional
left
ideals
containing
the
given
ideal.
It
generalizes
the
Beke-Schlesinger
algorithm
for
factoring
linear
ordinary
differential
operators,
and
uses
an
algorithm
for
finding
hyperexponental
solutions
of
such
ideals.
Keywords: differential operator, linear partial differential system, zero-dimensional left ideal, factorization. | |||
| Date | January 2002 | |||
| Comments | Has been submitted to ISSAC 2002 | |||
| Report | Factoring Zero-dimensional Ideals of Linear Partial Differential Operators (PDF) |
Compressed
PostScript: Factoring Zero-dimensional Ideals of Linear Partial Differential Operators (GZIP) | ||
| CS-2002-06 | ||||
|---|---|---|---|---|
| Title | Simplification of Definite Sums of Rational Functions | |||
| Authors | H.Q. Le | |||
| Abstract |
We
propose
an
algorithm
for
simplification
of
definite
sums
of
rational
functions
which,
for
a
given
input
rational
function
F(n,k),
constructs
two
rational
functions
G(n)
and
T(n,k)
such
that
n / n \
--- | --- |
\ | \ |
) F(n, k) = G(n) + | ) T(n, k)|
/ | / |
--- | --- |
k = 0 \ k = 0 /
where
the
degree
of
the
denominator
w.r.t.
k
of
T(n,k)
is
“small”.
| |||
| Date | # issued in January | |||
| Report | Simplification of Definite Sums of Rational Functions (PDF) |
Compressed
PostScript: Simplification of Definite Sums of Rational Functions (PS.Z) | ||
| CS-2002-05 | ||||
|---|---|---|---|---|
| Title | Fraction-free Row Reduction of Matrices of Skew Polynomials | |||
| Authors | Bernhard Beckermann, Howard Cheng, and George Labahn | |||
| Abstract | We present a new algorithm for row reduction of a matrix of skew polynomials. The algorithm can be used for finding full rank decompositions and other rank revealing transformations of such matrices. In particular these reductions can be applied to problems such as the desingularization of linear recurrence systems and for computing rational solutions of a large class of linear functional systems. The algorithm is suitable for computation in exact arithmetic domains where the growth of coefficients in intermediate computations is a central concern. This coefficient growth is controlled by using fraction-free methods. At the same time the method is fast: for an $m \times s$ matrix of input skew polynomials of degree $N$ with coefficients bounded by $K$ the algorithm has a worst case complexity of $O(m^5 s^4 (N+1)^4 K^2)$ bit operations. | |||
| Date | January 2002 | |||
| Comments | Submitted to: ISSAC 2002 | |||
| Report | Fraction-free Row Reduction of Matrices of Skew Polynomials (PS) | Fraction-free Row Reduction of Matrices of Skew Polynomials (PDF) |
Compressed
PostScript: Fraction-free Row Reduction of Matrices of Skew Polynomials (PS.Z) | |
| CS-2002-04 | ||||
|---|---|---|---|---|
| Title | A Modular Greatest Common Divisor Algorithm for Matrix Polynomials | |||
| Authors | Howard Cheng and George Labahn | |||
| Abstract | In this paper we give a modular algorithm to compute one-sided greatest common divisors for matrix polynomials, improving on the fraction-free algorithm by Beckermann and Labahn. We define lucky homomorphisms for the modular algorithm and give bounds on the coefficients in the results computed. In addition, the greatest common left (right) divisor computed by our algorithm is in column (row) reduced form. For computing a greatest common left divisor of two matrix polynomials of dimensions $m \times n_1$ and $m \times n_2$ having degree $N$ in which all the coefficients of the entries have sizes bounded by $K$, the bit complexity of our algorithm is $O(n(m^2N)^3 K^2)$ where $n = n_1+n_2$. This is a significant improvement over the fraction-free algorithm. Our algorithm also solves the extended one-sided GCD problem, and can be used to transform any matrix polynomial into column reduced form. | |||
| Date | January 2002 | |||
| Comments | Submitted to: ISSAC 2002 | |||
| Report | A Modular Greatest Common Divisor Algorithm for Matrix Polynomials (PDF) |
Compressed
PostScript: A Modular Greatest Common Divisor Algorithm for Matrix Polynomials (PS.Z) | ||
| CS-2002-03 | ||||
|---|---|---|---|---|
| Title | A reduced form for perturbed matrix polynomials | |||
| Authors | Claude-Pierre Jeannerod | |||
| Abstract |
We
show
that
every
perturbation
of
a
square
matrix
polynomial
with
zero
eigenvalues
only
can
be
reduced
by
equivalence,
under
certain
conditions,
to
a
perturbed
matrix
polynomial
whose
leading
matrix
has
maximal
Smith
form.
This
yields
a
reduced
form
for
square
perturbed
matrix
polynomials
from
which
one
can
easily
recover
all
the
eigenvalue
leading
terms
whose
exponent
is
the
inverse
of
a
positive
integer.
Key words: matrix polynomials, perturbed eigenvalues, Smith form, Newton diagram. | |||
| Date | January 2002 | |||
| Comments | Also available from the Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC'02), Lille, France, July 2002. | |||
| Report | A reduced form for perturbed matrix polynomials (PDF) |
Compressed
PostScript: A reduced form for perturbed matrix polynomials (GZIP) | ||
| CS-2002-02 | ||||
|---|---|---|---|---|
| Title |
On
integral
representation
and
algorithmic
approaches
to the evaluation of combinatorial sums | |||
| Authors | G.P. Egorychev and E.V. Zima | |||
| Abstract | Integral representation is applied to various problems of algorithmic indefinite and definite summation and for generating combinatorial identities. An integral representation approach to rational summation is compared to known algorithmic approaches. It is shown that the integral representation can be used for practical improvements of known summation algorithms. A new solution to Riordan's problem of combinatorial identities classification is presented. | |||
| Date | January 2002 | |||
| Report | On integral representation and algorithmic approaches to the evaluation of combinatorial sums (PS) | On integral representation and algorithmic approaches to the evaluation of combinatorial sums (PDF) |
Compressed
PostScript: On integral representation and algorithmic approaches to the evaluation of combinatorial sums (PS.Z) | |
| CS-2002-01 | ||||
|---|---|---|---|---|
| Title | A Graph Unification Machine for N.L. Parsing | |||
| Authors | V. Keselj and N. Cercone | |||
| Abstract | A simple, novel, and efficient computational model for a graph unification method for NL parsing is presented. We rely the body of existing research on labeled graph unification for natural language parsing. This model offers several advantages including: simplicity, efficiency, and amenability to a low-level, efficient, and straight-forward implementation. A consequence of this is that some earlier considerations with respect to garbage collection and redundant node copying become obsolete. The model uses a novel feature of sub-node structure sharing. | |||
| Date | January 2002 | |||
| Report | C and Java source code | A Graph Unification Machine for N.L. Parsing (PDF) |
Compressed
PostScript: A Graph Unification Machine for N.L. Parsing (PS.Z) | |