CS200243  

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) 
CS200242  

Title  A Highlevel 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 contextfree grammar (CFG) or forestregular 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 Highlevel Specification Language for Structured Document Transformation (PDF) 
CS200241  

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) 
CS200240  

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, XMLbased 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) 
CS200239  

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) 
CS200237  

Title  Fractionfree 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 fractionfree 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 fractionfree methods. The known factor can be predicted and removed efficiently. 

Date  November 2002  
Report  Fractionfree Row Reduction of Matrices of Ore Polynomials (PS)  Fractionfree Row Reduction of Matrices of Ore Polynomials (PDF) 
CS200236  

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 oneatatime 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 matchingbased executionapproach that we propose may be more efficient than the joinbased approaches.  
Date  November 2002  
Report  Optimizing Correlated Path Queries in XML Languages (PDF) 
CS200235  

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) 
CS200233  

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) 
CS200232  

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) 
CS200231  

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) 
CS200230  

Title  Streaming MPEG4 AudioVisual Objects with Quality Adaptation  
Authors  Toufik Ahmed (1),(2), Youssef Iraqi (1), Raouf Boutaba (1) and Ahmed Mehaoua (2)  
Abstract  This paper presents an Objectbased Quality Adaptation Mechanism (OQAM) for streaming unicast MPEG4 AudioVisual content over the Internet. This mechanism dynamically adds and drops MPEG4 AudioVisual Objects (AVOs) by using a TCPFriendly 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 audiovisual quality. This endtoend 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 MPEG4 AudioVisual Objects with Quality Adaptation (PDF) 
CS200229  

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 nearinfrared 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) 
CS200226  

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) RungeKutta 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) 
CS200225  

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) 
CS200223  

Title  On the Equivalence Between Prony's and BenOr's/Tiwari's Methods  
Authors  Mark Giesbrecht, George Labahn, Wenshin 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, BenOr/Tiwari algorithm, exponential functions. 

Date  July 2002  
Report  On the Equivalence Between Prony's and BenOr's/Tiwari's Methods (PS)  On the Equivalence Between Prony's and BenOr's/Tiwari's Methods (PDF) 
CS200222  

Title  SNAP User's Guide  
Authors  ClaudePierre Jeannerod, George Labahn,  
Abstract  In this paper we describe the SNAP (SymbolicNumeric 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) 
CS200221  

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 
CS200217  

Title  State of the Art in the Realistic Simulation of Plant Leaf Venation Systems  
Authors  Julia TaylorHell 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) 
CS200216  

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 physicallybased 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) 
CS200214  

Title  A Formal Analysis of the WillRetire 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 singlestep 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 200211 and includes little introductory material.  
Date  March 2002  
Report  A Formal Analysis of the WillRetire Correctness Statement (PS)t  A Formal Analysis of the WillRetire Correctness Statement (PDF) 
CS200213  

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 MaximumQuartetConsistency 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) 
CS200211  

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 outoforder 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 toplevel 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) 
CS200210  

Title  HighOrder Lifting  
Authors  Arne Storjohann  
Abstract  The wellknown technique of adiclifting for linearsystem 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/ Smithform computation. All algorithms are Las Vegas probabilistic.  
Date  # issued in February  
Comments  Submitted to: ISSAC '02  
Report  HighOrder Lifting (PDF)  Compressed PostScript: HighOrder Lifting (PS.Z) 
CS200207  

Title  Factoring Zerodimensional Ideals of Linear Partial Differential Operators  
Authors  Ziming Li, Fritz Schwarz, Serguei P Tsarev  
Abstract  This paper presents an algorithm for factoring a zerodimensional 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 finitedimensional over the field of constants. The algorithm computes all the zerodimensional left ideals containing the given ideal. It generalizes the BekeSchlesinger 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, zerodimensional left ideal, factorization. 

Date  January 2002  
Comments  Has been submitted to ISSAC 2002  
Report  Factoring Zerodimensional Ideals of Linear Partial Differential Operators (PDF)  Compressed PostScript: Factoring Zerodimensional Ideals of Linear Partial Differential Operators (GZIP) 
CS200206  

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) 
CS200205  

Title  Fractionfree 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 fractionfree 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  Fractionfree Row Reduction of Matrices of Skew Polynomials (PS)  Fractionfree Row Reduction of Matrices of Skew Polynomials (PDF)  Compressed PostScript: Fractionfree Row Reduction of Matrices of Skew Polynomials (PS.Z) 
CS200204  

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 onesided greatest common divisors for matrix polynomials, improving on the fractionfree 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 fractionfree algorithm. Our algorithm also solves the extended onesided 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) 
CS200203  

Title  A reduced form for perturbed matrix polynomials  
Authors  ClaudePierre 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) 
CS200202  

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) 
CS200201  

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 lowlevel, efficient, and straightforward 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 subnode 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) 