| CS-99-27 | ||||
|---|---|---|---|---|
| Title | The Making of a Geometric Algebra Package in Matlab | |||
| Authors | Stephen Mann, Leo Dorst, and Tim Bouma | |||
| Abstract | In this paper, we describe our development of GABLE, a Matlab implementation of the Geometric Algebra based on cl_{p,q} (where p+q=3) and intended for tutorial purposes. Of particular note are the matrix representation of geometric objects, effective algorithms for this geometry (inversion, Meet and Join), and issues in efficiency and numerics. | |||
| Report | The Making of a Geometric Algebra Package in Matlab (PDF) |
Compressed
PostScript: The Making of a Geometric Algebra Package in Matlab (GZIP) | ||
| CS-99-26 | ||||
|---|---|---|---|---|
| Title | Stefy: Java Parser for HPSGs, Version 0.1 | |||
| Authors | Vlado Keselj | |||
| Abstract | This document describes design and implementation of the system Stefy--a Java parser for Head-Driven Phrase Structure Grammars (HPSG). The parser is used in an Internet information retrieval system. | |||
| Report | Stefy: Java Parser for HPSGs, Version 0.1 (PDF) |
Compressed
PostScript: Stefy: Java Parser for HPSGs, Version 0.1 (PS.Z) | ||
| CS-99-24 | ||||
|---|---|---|---|---|
| Title | Health Informatics Education Working Paper | |||
| Authors | H. D. Covvey and A. B. Pidduck | |||
| Date | September 20, 1999 | |||
| Report | Health Informatics Education Working Paper (PDF) | |||
| CS-99-23 | ||||
|---|---|---|---|---|
| Title | A Framework for Software Architecture Verification | |||
| Authors | K. Lichtner, P. Alencar and D.D. Cowan | |||
| Date | July 1999 | |||
| Report | A Framework for Software Architecture Verification (PS) | |||
| CS-99-22 | ||||
|---|---|---|---|---|
| Title | An Abel ODE class generalizing known integrable classes | |||
| Authors | E.S. Cheb-Terrab and A.D. Roche | |||
| Abstract | A multi-parameter non-constant invariant Abel ODE class with the following remarkable features is presented. This one class is shown to generalize, that is, contain as particular cases, all the integrable classes presented by Abel, Liouville and Appell, as well as all those shown in Kamke's book and various other references. In addition, the class being presented includes other new and fully integrable subclasses, as well as the most general parameterized class we know of whose members can systematically be mapped into Riccati type ODEs. Finally, many integrable members of this class can be systematically mapped into an integrable member of a different class; leading in this way to new integrable classes from previously known ones. | |||
| Date | Aug 24 1999 | |||
| Comments | This paper has been submitted to The European Journal of Applied Mathematics, August 1999 | |||
| Report | An Abel ODE class generalizing known integrable classes (DVI) | An Abel ODE class generalizing known integrable classes (PDF) | An Abel ODE class generalizing known integrable classes (ZIP) | |
| CS-99-21 | ||||
|---|---|---|---|---|
| Title | Abel ODEs: Equivalence and Integrable Classes | |||
| Authors | E.S. Cheb-Terrab and A.D. Roche | |||
| Abstract | A classification, according to invariant theory, of non-constant invariant Abel ODEs known as solvable and found in the literature is presented. A set of new integrable classes depending on one or no parameters, derived from the analysis of the works by Abel, Liouville and Appell, is also shown. Computer algebra routines were developed to solve any member of these classes by solving its related equivalence problem. The resulting library permits the systematic solving of Abel type ODEs in the Maple symbolic computing environment. | |||
| Date | Aug 24 1999 | |||
| Comments | This paper has been submitted to Computer Physics Communications, July 1999 | |||
| Report | Abel ODEs: Equivalence and Integrable Classes (DVI) | Abel ODEs: Equivalence and Integrable Classes (PDF) | Abel ODEs: Equivalence and Integrable Classes (ZIP) | |
| CS-99-20 | ||||
|---|---|---|---|---|
| Title | Numeric and Symbolic Computation of Problems defined by Structured Linear Systems | |||
| Authors | B. Beckermann and G. Labahn | |||
| Abstract |
This
paper
considers
the
problem
of
effective
algorithms
for
some
problems
having
structured
coefficient
matrices.
Examples
of
such
problems
include
rational
approximation
and
rational
interpolation.
The
corresponding
coefficient
matrices
include
Hankel,
Toeplitz
and
Vandermonde-like
matrices.
Effective
implies
that
the
algorithms
studied
are
suitable
for
implementation
in
either
a
numeric
environment
or
else
a
symbolic
environment. The paper includes two algorithms for the computation of rational interpolants which are both effective in symbolic environments. The algorithms use arithmetic that is free of fractions but at the same time control the growth of coefficients during intermediate computations. One algorithm is a look-around procedure which computes along a path of closest normal points to an offdiagonal path while the second computes along an arbitrary path using a look-ahead strategy. Along an antidiagonal path the look-ahead recurrence is closely related to the Subresultant PRS algorithm for polynomial GCD computation. Both algorithms are an order of magnitude faster than alternate methods which are effective in symbolic environments. | |||
| Date | August 1999 | |||
| Report | Numeric and Symbolic Computation of Problems defined by Structured Linear Systems (PDF) | |||
| CS-99-19 | ||||
|---|---|---|---|---|
| Title | Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time | |||
| Authors | T. Biedl | |||
| Abstract | We study the problem of finding large independent sets in planar graphs in linear time. By modifying the traditional greedy-method, we show how to obtain an independent set of size at least 5/23 n in linear time. This falls short of the independent set of size 1/4 n, which is known to exist by the 4-color theorem, but is an improvement over the 1/5 n bound of the best known linear-time heuristic. We also study independent sets where vertices have bounded degree, and obtain for D >6 at least min { 5/23 n, (D-6)/(4D-18) n } independent vertices of degree < D in linear time. | |||
| Date | July 1999 | |||
| Comments | A two-page abstract of this paper has been submitted at SODA'2000 (Symposium on Discrete Algorithms). | |||
| Report | Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time (PDF) |
Compressed
PostScript: Large Independent Sets and Low-Degree Independent Sets in Planar Graphs in Linear Time (PS.Z) | ||
| CS-99-17 | ||||
|---|---|---|---|---|
| Title | Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids | |||
| Authors | J. Shallit and D. Hamm | |||
| Date | July 1999 | |||
| Report | Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids (PDF) | Compressed PostScript:Characterization of Finite and One-Sided Infinite Fixed Points of Morphisms on Free Monoids (PS.Z) | ||
| CS-99-16 | ||||
|---|---|---|---|---|
| Title | An Evolutionary Approach to Structural Design Composition | |||
| Authors | Paulo Alencar, Donald Cowan, Jing Dong, Carlos Lucena | |||
| Abstract | One of the main goals of component-based software engineering (CBSE) is to enable automated assembly of software components, thus bringing greater quality and reliability, reducing development and test times, increasing productivity from multiple use of software components in the software development. A serious impediment for component assembly is due to the fact that the design and architectural assumptions that a reusable component makes about the structure of the application are in most cases implicit, lost or buried in complex implementation structures. In this paper we present an evolutionary approach to support the creation of reusable and changeable software architectures which focuses on the structural compositon of components at the design level. The architectural design information, captured by design patterns, is made explicit and represented in a declarative way, being packaged into tangible artifacts as building block design components in the development process. In this way, the declarative design component representations can be instantiated, adapted, assembled, maintained, and implemented. Furthermore, we can also use these representations to reason about properties related to the combination of design components. Our approach is illustrated through a case study involving various design patterns | |||
| Report | An Evolutionary Approach to Structural Design Composition (PDF) | |||
| CS-99-15 | ||||
|---|---|---|---|---|
| Title | Containment and Optimization of Object-Preserving Conjunctive Queries | |||
| Authors | E.P.F. Chan and R. van der Meyden | |||
| Date | February 1999 | |||
| Report | Containment and Optimization of Object-Preserving Conjunctive Queries (PDF) |
Compressed
PostScript: Containment and Optimization of Object-Preserving Conjunctive Queries (GZIP) | ||
| CS-99-14 | ||||
|---|---|---|---|---|
| Title | Better Pasting Through Quasi-Interpolation | |||
| Authors | B. Conrad | |||
| Abstract |
Hierarchical
surface
pasting,
developed
by
Barghiel,
Bartels
and
Forsey,
is
an
interactive
surface
modelling
technique
that
is
used
to
add
local
detail
to
a
tensor
product
B-spline
surface
without
increasing
the
overall
complexity
of
the
original
surface.
Surface
pasting
approximates
displacement
mapped
surfaces
by
placing
additional
tensor
product
surfaces,
called
features,
on
the
base
surface.
The
features
may
be
scaled,
rotated,
and
translated
arbitrarily
over
the
base
surface,
and
the
composite
surface
can
be
evaluated
using
relatively
little
computational
power.
Because
the
feature
only
approximates
a
displacement
map,
a
surface
produced
using
standard
surface
pasting
often
has
noticeable
gaps
at
the
edges
of
the
pasted
feature.
The
severity
of
the
surface
discontinuities
may
be
made
as
small
as
desired
via
knot
insertion,
but
this
can
result
in
an
unacceptable
degradation
in
the
performance
of
the
modelling
software. Quasi-interpolation is an approximation method that approximates curves with spline curves to a high degree of accuracy. The approximation is constructed by computing coefficients that are used to weight samplings of the curve to be approximated. The Lyche-Schumaker quasi-interpolant uses coefficients that are inexpensive to compute and samplings that are relatively expensive to compute. I propose an improved surface pasting technique that uses quasi-interpolation to set the feature's boundary control vertices. For surface pasting it is necessary to have quasi-interpolants that reproduce position and derivatives at the endpoints of the curve to be approximated. In addition, as the feature surface is moved, the curve samplings must be recomputed, but the coefficients remain fixed. Therefore, I have developed a variation of the quasi-interpolant whose coefficients are expensive to compute, but whose samplings are relatively inexpensive to compute. Surface pasting with quasi-interpolation produces features whose boundaries approximate the base surface to within the same tolerance as those produced by standard pasting, but with one third the boundary control vertices. The resulting feature has one ninth the total control vertices and can be constructed in approximately one tenth the time as with standard surface pasting. | |||
| Date | May 1999 | |||
| Report | CS-99-14 (PDF) |
Compressed
PostScript: CS-99-14 (PS.Z) | ||
| CS-99-13 | ||||
|---|---|---|---|---|
| Title | Cylindrical Surface Pasting | |||
| Authors | S. Mann and T.P.-Y. Yeung | |||
| Abstract |
The
idea
of
hierarchical
modelling
is
that
many
surfaces
have
different
levels
of
detail
and
for
modelling
purposes
it
is
useful
to
interactively
edit
these
surfaces
at
any
level
of
detail.
Detail
can
be
added
to
tensor-product
B-spline
via
knot
insertion,
but
once
the
detail
has
been
added
the
the
surface
can
not
be
edited
at
a
lower
level
of
detail.
Hierarchical
B-splines
were
designed
to
allow
for
a
type
of
knot
insertion
method
that
still
admits
editing
the
surface
at
any
level
of
detail.
However,
the
details
can
not
be
rotated,
nor
is
it
convenient
to
create
a
library
of
such
details.
Surface
pasting
is
a
generalization
of
hierarchical
B-splines
that
allows
for
the
creation
of
a
feature
library,
and
where
the
pasted
features
can
be
rotated
and
scaled,
and
translated
across
the
base
surface. Cylindrical pasting is a parametric-blending method that creates a smooth transition surface between a pair of B-spline surfaces that do not originally intersect. This blending surface is a deformed cylinder, and its creation is based on the surface pasting composition method, which adds detailed features to base surfaces by means of an efficient displacement method. In cylindrical pasting, a transition cylinder can be pasted on a NUBS surface or onto a NUBS cylinder. A displacement scheme is used to locate the control points of the blending cylinder to achieve approximate $C^1$ continuity between the boundaries of the base surfaces and the edges of the cylinders. | |||
| Date | May 1999 | |||
| Report | Cylindrical Surface Pasting (PDF) |
Compressed
PostScript: Cylindrical Surface Pasting (PS.Z) | ||
| CS-99-12 | ||||
|---|---|---|---|---|
| Title | Multi-scale R-tree | |||
| Authors | E.P.F. Chan and K.K.W. Chow | |||
| Date | April 1999 | |||
| Report | Multi-scale R-tree (PDF) |
Compressed
PostScript: Multi-scale R-tree (PS.Z) | ||
| CS-99-09 | ||||
|---|---|---|---|---|
| Title | Resizable Arrays in Optimal Time and Space | |||
| Authors | A. Brodnik, S. Carlsson, E.D. Demaine, J.I. Munro and R. Sedgewick | |||
| Abstract | We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l...l+n-1], of fixed-size elements, as elements are added to or removed from one or both ends. In addition to these operations, our data structures support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(sqrt(n)) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2^k - c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques. | |||
| Date | September 2000 | |||
| Comments | A short version of this paper appears in Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), edited by Frank Dehne, Arvind Gupta, Jvrg-R|diger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, volume 1663, Vancouver, British Columbia, Canada, August 11-14, 1999, pages 37-48. | |||
| Report | Resizable Arrays in Optimal Time and Space (PDF) |
Compressed
PostScript: Resizable Arrays in Optimal Time and Space (GZIP) | ||
| CS-99-05 | ||||
|---|---|---|---|---|
| Title | Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories | |||
| Authors | P.R. Sidorowicz | |||
| Abstract |
An
evaluation
of
well-known
tests:
Mats+,
Mats++,
March
Y
and
March
C-
with
respect
to
input
stuck-at
faults
in
a
n-word
by
l-bit
static
CMOS
random-access
memory
(SRAM)
array
is
presented.
First,
an
SRAM
cell's
behavior
is
analysed
at
the
transistor-network,
event-sequence,
and
finite-state
machine
(FSM)
level.
Then,
an
input
stuck-at
fault
model
for
an
SRAM
is
defined.
We
show
that
the
word
oriented
extensions
of
the
above-mentioned
tests
detect
reliably
at
most
(n+4l)/(2n+4l)*100%
of
faults
in
our
fault
model,
which
for
large
n
constitutes
roughly
50%
of
faults.
We
propose
a
DFT
enhancement
that
would
increase
this
coverage
to
100%. Keywords:CMOS, design for testability, fault modelling, March C-, March Y, Mats+, Mats++, SRAM, stuck-at faults, testing. | |||
| Date | March 1999 | |||
| Comments | This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871. | |||
| Report | Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories (PDF) |
Compressed
PostScript: Evaluating Tests for Input Stuck-at Faults in Word-Oriented Static Random-Access Memories (PS.Z) | ||
| CS-99-04 | ||||
|---|---|---|---|---|
| Title | Ununfoldable Polyhedra | |||
| Authors |
Marshall
Bern
(Xerox
PARC) Erik D. Demaine (University of Waterloo) David Eppstein (University of California, Irvine) Eric Kuo (MIT) | |||
| Abstract | A well-studied problem is that of unfolding a convex polyhedron into a simple planar polygon. In this paper, we study the limits of unfoldability. We give an example of a polyhedron with convex faces that cannot be unfolded by cutting along its edges. We further show that such a polyhedron can indeed be unfolded if cuts are allowed to cross faces. Finally, we prove that "open'' polyhedra with convex faces may not be unfoldable no matter how they are cut. | |||
| Date | August 1999 | |||
| Comments |
This
paper
appears
in
the
electronic
proceedings
of
the
11th
Canadian
Conference
on
Computational
Geometry
(CCCG'99),
Vancouver,
British
Columbia,
Canada,
August
15-18,
1999. We are pursuing these problems further; please contact the authors if you make any progress. | |||
| Report | Ununfoldable Polyhedra (PDF) |
Compressed
PostScript: Ununfoldable Polyhedra (PS.Z) | ||
| CS-99-03 | ||||
|---|---|---|---|---|
| Title | Convexifying Monotone Polygons | |||
| Authors |
Therese
C.
Biedl
(University
of
Waterloo) Erik D. Demaine (University of Waterloo) Sylvain Lazard (INRIA Lorraine) Steven M. Robbins (McGill University) Michael A. Soss (McGill University) | |||
| Abstract | This paper considers reconfigurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can reconfigure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in O(n^2) time a sequence of O(n^2) moves, each of which rotates just four joints at once. | |||
| Date | December 1999 | |||
| Comments |
A
version
of
this
paper
appears
in
Proceedings
of
the
10th
Annual
International Symposium on Algorithms and Computation (ISAAC'99), Lecture Notes in Computer Science, Springer-Verlag, volume 1741, Chennai, India, December 16-18, 1999, pages 415-424. | |||
| Report | Convexifying Monotone Polygons (PDF) |
Compressed
PostScript: Convexifying Monotone Polygons (PS.Z) | ||
| CS-99-02 | ||||
|---|---|---|---|---|
| Title | Hardware Rendering with Bidirectional Reflectances | |||
| Authors | J. Kautz and M. McCool | |||
| Abstract |
A
separable
decomposition
of
bidirectional
reflectance
distributions
(BRDFs)
is
used
to
implement
arbitrary
reflectances
from
point
sources
on
existing
graphics
hardware.
Two-dimensional
texture
mapping
and
compositing
operations
are
used
to
reconstruct
samples
of
the
BRDF
at
every
pixel
at
inter-
active
rates. A change of variables, the Gram-Schmidt halfangle/difference vector parameterization, improves separability in the case of near-specular BRDFs. Two decomposition algorithms are also presented. The singular value decomposition (SVD) minimizes RMS error. The normalized decomposition is fast, simple, and online, using no more space than what is required for the final representation. | |||
| Date | February 1999 | |||
| Comments | There is a website which contains more information on this and other rendering projects in CGL. | |||
| Report | Hardware Rendering with Bidirectional Reflectances (PDF) | Hardware Rendering with Bidirectional Reflectances (README) | ||
| CS-99-01 | ||||
|---|---|---|---|---|
| Title | Ptolemy: A Programmer's Manual | |||
| Authors | K.W. Parker | |||
| Abstract | Ptolemy is a prototype subsystem for the automatic set up of the numerical solution of Partial Differential Equations via sinc-collocation. Sinc collocation is a procedure for applying a change of variable such that spectral approximation is ultra efficient. As a result the setup process involves significant symbolic computation. | |||
| Date | January 1999 | |||
| Report | Ptolemy: A Programmer's Manual (PDF) |
Compressed
PostScript: Ptolemy: A Programmer's Manual (GZIP) | ||