Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.ai.toronto.edu!csri.toronto.edu!diana From: diana@csri.toronto.edu (Diana Li) Newsgroups: ont.events Subject: B.N. Parlett, Friday 28 July 1989: NUMERICAL ANALYSIS SEMINAR Message-ID: <8907181319.AA04229@king.csri.toronto.edu> Date: 18 Jul 89 13:20:41 GMT Lines: 125 ACTIVITIES FOR THE WEEK COMMENCING JULY 24, 1989 (SF = Sandford Fleming Building, 10 King's College Road) ------------------------------------------------------------- NUMERICAL ANALYSIS SEMINAR SF 1101, at 2:10 p.m., Tuesday 25 July 1989 Vivette Girault Laboratorie d'Analyse Numerique, University of Paris VI "Steady-State Stokes Flow in Two or Three-Dimensional Exterior Domains" We consider the solution of the steady-state Stokes flow, in two and three dimensions, on the exterior of a bounded domain. By imposing the appropriate behaviour of the velocity at infinity, the problem can posed in a variational form with a unique solution. If the external forces have bounded support it is possible to solve the problem by coupling a finite element method in the bounded region supporting f, with boundary integral equations. ------------------------------------------------------------- AI SEMINAR SF 3202, at 11:00 a.m., Wednesday 26 July 1989 Marc Linster Gesellschaft fur Mathematik und Datenverarbeitung, West Germany "From KRITON to IRMA: Two Paradigms for Automated Knowledge Acquisition" GMD's project KRITON is concerned with basic research in the domain of automated and computer-supported knowledge acquisition. After a short presentation of GMD and its Institute for Applied Information Technology we will describe the projects of the expert system research group that constitute the context of the KRITON project. I will first present and critique the knowledge-acquisition system KRITON that integrates two techniques originating from cognitive psychology, i.e. interview techniques and protocol analysis. The KRITON-system is based on a bottom-up approach, i.e. it focuses on the support of rapid prototyping. The second approach I will present is based on the KADS-knowledge-models (Knowledge Acquisition and Design Structuring) and on our experience with the techniques that were originally developed for the KRITON-system. This approach is best described as model-guided knowledge acquisition. The system that will result from the integration of knolwedge-modeling with knowledge acquisition will be called IRMA (Interpretation, Representation, Modeling and Acquisition). IRA-grid (Interpretation, Representation and Acquisition using repertory-grids) is the first component of IRMA. It is a knowledge-acquisition tool that tries to acquire the knowledge needed for hypothesis-selection processes. ------------------------------------------------------------- THEORY SEMINAR SF 3202, at 2:00 p.m., Wednesday 26 July 1989 Noga Alon Tel Aviv University & Bell Communications Research "Balancing Vectors with Applications in Communication Theory" Let F=F(n) denote the set of all vectors with coordinates +1 or -1 in the n dimensional Euclidean space. We show that for every even n the minimum cardinality of a subset S of F such that for every vector in F there is a member of S orthogonal to it, is precisely n. This result and some of its extensions have certain applications to communication theory. (Joint work with Bergmann, Coppersmith and Odlyzko.) ------------------------------------------------------------- THEORY SEMINAR SF 1101, at 2:00 p.m., Thursday 27 July 1989 Michael Saks Univeristy of California, San Diego "The Cell-probe Complexity of Dynamic Data Structures" The typical dynamic data storage and retrieval problem requires maintenance of a data set in a way that permits certain types of changes in the data set (updates) and queries about the data. One simple example is the interval range-query problem: maintain a subset S of the integers 1 to n, allowing updates of the form: given a specific element, add it to S if it is not in and delete it otherwise, and queries of the form: how many elements of the set are between i and j? For many such problems there appears to be an inherent trade-off between the costs of updates and queries. Here a new method for proving such tradeoffs is presented, which can be used to give nearly tight tradeoffs for the interval range query problem and several other problems, including partial sum-queries, dynamic-list ranking, and disjoint set union-find. The lower bounds are proved in Yao's cell-probe model which does not assume restrictions on the representation of the data or on the operations allowed and are based only on the number of write operations needed for an update versus the number of read operations needed for a query. The lower bounds hold for amortized as well as worst case complexity, and apply to randomized as well as deterministic algorithms. (Joint work with Michael Fredman.) ------------------------------------------------------------- NUMERICAL ANALYSIS SEMINAR SF 1105, at 2:10 p.m., Friday 28 July 1989 B.N. Parlett University of California at Berkeley "Isospectral Flows and Forward Instability of the QR Algorithm" We describe the connection between certain systems of nonlinear differential equations and the QR algorithm for transforming a square matrix to upper triangular form. The QR algorithm is backward stable. We describe conditions under which it is forward stable. We mention recent results of Batterson and Smillie showing the QR with Rayleigh quotient shifts can cycle and even behave chaotically.