clarke@utcsri.UUCP (Jim Clarke) (11/20/86)
(GB = Galbraith Building, 35 St. George Street)
(SF = Sanford Fleming Building, 10 King's College Road)
NUMERICAL ANALYSIS - Tuesday, November 25, 2 p.m., GB 120
Professor Nezam Mahdavi-Amiri
Modelling Optimization Test Problems with a
Finite Number of Characterized Points
(abstract below)
AI - Tuesday, November 25, 3 p.m., GB 119
Professor Z. Stachniak
Computational Logics and Computational Semantics
(abstract below)
GRAPH THEORY - Tuesday, November 25, 4 p.m., GB 120
Professor Joseph W.H. Liu
Trees in Sparse Matrix Computation
(abstract below)
SYSTEMS SEMINAR - Thursday, November 27, 11 a.m., SF 1101
Professor Jia Xu
The Performance vs. Computation Time Tradeoff in
Database Concurrency Control
(abstract below)
THEORY - Thursday, November 27, 3 p.m., GB 220
Professor A. Mirzaian
Algorithmic Applications of the Halving Method
(abstract below)
ABSTRACTS
Modeling Optimization Test Problems with a
Finite Number of Characterized Points
Professor Nezam Mahdavi-Amiri
Optimization test problems are needed to investigate computational and
theoretical issues in the development of optimization algorithms. We give
a methodology by which various nonlinear models can be constructed. Given
an objective function and the constraints (if any), we augment the problem
with linear and or nonlinear terms to meet specifications such as function
and Lagrangian values, their gradients and Hessians, at a finite number of
points. This enables the user to create features of conditioning,
activity, stationarity, feasibility and optimality. Moreover, degenerate
test problems as well as problems whose projected Lagrangian Hessians are
characterized may be constructed. These features provide for the creation
of test problems with a wide range of numerical properties at a finite
number of points.
Computational Logics and Computational Semantics
Professor Z. Stachniak
The growing number of applications of formal logical systems in Com-
puter Science calls for a uniform methodological approach to the computa-
tional aspects of theorem proving. In the talk the general concepts of a
computational logic and computational semantics will be discussed. It will
be shown that every computational logic has a truth-table theorem checking
decision procedure.
Trees in Sparse Matrix Computation
Professor Joseph W.H. Liu
In this talk, we survey the recent developments in the use of tree
structures in the solution of large sparse linear systems. The elimination
tree structure is introduced and some of its basic properties relevant to
sparse matrix factorization are discussed. It is useful in the characteri-
zation of a class of equivalent reorderings, equivalent in terms of fills
and operation counts. We consider its important role in many sparse fac-
torization algorithms on different machine configurations: multifrontal
methods, out-of-core schemes, paging environment, parallel/vector architec-
tures. We also relate some graph-theoretic algorithms with sparse matrix
computation in the context of this elimination tree.
The Performance vs. Computation Time
Tradeoff in Database Concurrency Control
Professor Jia Xu
A major issue in the theory of database concurrency control is how to
optimize performance while guaranteeing correctness of a database system.
We consider the performance vs. computation time tradeoff involved in data-
base concurrency control. The objective of this study is to systematically
categorize limits of performance achievable by polynomial time database
concurrency control algorithms. Towards this objective, a formal model is
introduced which captures the dynamic aspects of on-line concurrency con-
trol, and contains only a minimum set of built-in constraints necessary for
guaranteeing serializability. This allows one to determine in a uniform
framework precise complexity boundaries for problems of using various
optimizing strategies for enhancing performance while guaranteeing correct-
ness of a database system.
Algorithmic Applications of the Halving Method
Professor A. Mirzaian
The "halving" technique is a recently developed algorithmic paradigm.
After a brief introduction to this simple technique, the following applica-
tions will be described: (i) the longest regular subsequence problem, (ii)
selection in sorted matrices, (iii) optimum offset in VLSI river routing.
The resulting algorithms are simple and improve the running time of previ-
ously known results.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke