1999 Technical Reports | SCS | UW
[Please remove <h1>]
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-99-24 |
| Title |
Health Informatics Education Working Paper |
| Authors |
H. D. Covvey and A. B. Pidduck |
| Abstract |
|
| Date |
September 20, 1999 |
| Comments |
|
| Report |
|
|
Adobe
PDF |
|
| CS-99-23 |
| Title |
A Framework for Software
Architecture Verification |
| Authors |
K. Lichtner, P. Alencar
and D.D. Cowan |
| Date |
July 1999 |
| Report |
|
PostScript |
|
|
| 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 |
Latex |
|
Adobe
PDF |
Compressed
Latex and PostScript |
| 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 |
Latex |
|
Adobe
PDF |
Compressed
Latex and PostScript |
| 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 |
|
|
Adobe
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 2-page abstract of this
paper has been submitted at SODA'2000 (Symposium on Discrete Algorithms). |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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
|
| Date |
|
| Comments |
|
| Report |
|
|
Adobe
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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| CS-99-13 |
| Title |
Cylindrical Surface Pasting |
| Authors |
S. Mann and T.P.-Y. Yeung |
| Abstract |
The idea of hierarchical
modeling is that many surfaces have different levels of detail and for modeling
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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 modeling, 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 web
sitewhich contains more information on this and other rendering projects
in CGL.
|
| Report |
|
|
Adobe
PDF |
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 |
|
|
Adobe
PDF |
Compressed
PostScript |