Newsgroups: ont.events Path: utzoo!utgpu!jarvis.csri.toronto.edu!csri.toronto.edu!clarke From: clarke@csri.toronto.edu (Jim Clarke) Subject: (none) Message-ID: <1988Feb18.114115.16657@jarvis.csri.toronto.edu> Organization: University of Toronto, AI group Date: Thu, 18-Feb-88 11:41:14 EST Newsgroups: ont.events Subject: U of Toronto Computer Science activities, Feb. 22-26 Organization: University of Toronto, CSRI Distribution: ont (SF = Sandford Fleming Building, 10 King's College Road) (GB = Galbraith Building, 35 St. George Street) (WB = Wallberg Building, 184 College Street) SUMMARY: NUMERICAL ANALYSIS SEMINAR, Tuesday, February 23, 10 am, WB242 -- Uri Ascher: "On Numerical Differential-Algebraic Problems With Application to Semiconductor Device Simulation" AI/SYSTEMS/THEORY SEMINAR, Tuesday, Feb. 23, 11 am, SF1105 -- Joseph Halpern: "Reasoning about knowledge and probability" A.I. SEMINAR, Tuesday, February 23, 2 pm, SF1105 -- Elisha Sacks: "Automatic Qualitative Analysis of Ordinary Differential Equations Using Piecewise Linear Approximations" GRAPH/THEORY SEMINAR, Tuesday, February 23, 3 pm, GB120 -- Michael Luby: "Grid Geometries Which Preserve Properties Of Euclidean Geometry: A Study Of Graphics Line Drawing Algorithms" SYSTEMS SEMINAR, Thursday, February 25, 11 am, SF1101 -- William Pugh: "Incremental Evaluation of Functional Programs" NUMERICAL ANALYSIS SEMINAR, Friday, Feb. 26, 3 pm, GB220 -- Kurt Anstreicher: "A Survey of Existing Versions of Karmarkar's Algorithm" ------------------------------- NUMERICAL ANALYSIS SEMINAR, Tuesday, February 23, 10 am, WB242 Professor Uri Ascher University of British Columbia "On Numerical Differential-Algebraic Problems With Application to Semiconductor Device Simulation" This talk considers questions of conditioning of and numerical methods for certain differential algebraic equations subject to initial and boundary conditions. The approach taken is that of separating differential and algebraic solution components, at least theoretically. This yields conditioning results for differential algebraic boundary value problems in terms of pure differential problems, for which existing theory is well-developed. We carry the process out for problems with (global) index 1 or 2. For semi-explicit boundary value problems of index 1 (where solution com- ponents are separated) we give a convergence theorem for a special class of collocation methods. For initial value problems with index 2 we discuss the use of BDF schemes, summarizing conditions for their successful and stable utilization. Finally, the present considerations and analysis are applied to problems involving differential-algebraic equations which arise in semiconductor device simulation. AI/SYSTEMS/THEORY SEMINAR, Tuesday, February 23, 11 am, SF1105 Dr. Joseph Y. Halpern IBM Almaden Research Centre "Reasoning about knowledge and probability" Reasoning about knowledge is an area of active research in both AI and dis- tributed systems. In many application areas, it is important to be able to reason about probabilistic events as well. We provide a model for reason- ing about knowledge and probability together. We allow explicit mention of probabilities in formulas, so that our language has formulas that essen- tially say ``according to agent I, formula F holds with probability at least A.'' The language is powerful enough to allow reasoning about higher-order probabilities, as well as allowing explicit comparisons of the probabilities an agent places on distinct events. We present a general framework for interpreting such formulas, and consider various properties that might hold of the interrelationship between agents' subjective probability spaces at different states. We briefly describe a number of technical results, including a complete axiomatization and decision procedures. The talk is completely self-contained. This is joint work with Ron Fagin. A.I. SEMINAR, Tuesday, February 23, 2 pm, SF1105 Dr. Elisha Sacks M.I.T. "Automatic Qualitative Analysis of Ordinary Differential Equations Using Piecewise Linear Approximations" This talk explores automating the qualitative analysis of physical systems. Scientists and engineers model many physical systems with ordinary dif- ferential equations. They deduce the behavior of the systems by analyzing the equations. Most realistic models are nonlinear, hence difficult or impossible to solve explicitly. Analysts must resort to approximations or to sophisticated mathematical techniques. I describe a program, called PLR (for Piecewise Linear Reasoner), that formalizes an analysis strategy employed by experts. PLR takes parameterized ordinary differential equa- tions as input and produces a qualitative description of the solutions for all initial values. It approximates intractable nonlinear systems with piecewise linear ones, analyzes the approximations, and draws conclusions about the original systems. It chooses approximations that are accurate enough to reproduce the essential properties of their nonlinear prototypes, yet simple enough to be analyzed completely and efficiently. PLR uses the standard phase space representation. It builds a composite phase diagram for a piecewise linear system by pasting together the local phase diagrams of its linear regions. It employs a combination of geometric and algebraic reasoning to determine whether the trajectories in each linear region cross into adjoining regions and summarizes the results in a transition graph. Transition graphs explicitly express many qualita- tive properties of systems. PLR derives additional properties, such as boundedness or periodicity, by theoretical methods. PLR's analysis depends on abstract properties of systems rather than on specific numeric values. This makes its conclusions more robust and enables it to handle parameter- ized equations transparently. I demonstrate PLR on several common non- linear systems and on published examples from mechanical engineering. GRAPH/THEORY SEMINAR, Tuesday, February 23, 3 pm, GB120 Professor Michael Luby University of Toronto "Grid Geometries Which Preserve Properties Of Euclidean Geometry: A Study Of Graphics Line Drawing Algorithms" The motivating problem for this work is how to display straight line seg- ments on a graphics screen. Each line segment in the Euclidean plane is displayed on the screen as a path of "on" pixels in a grid. A grid geometry, which specifies a unique path along grid edges between every pair of grid points, is the analog of Euclidean geometry in graphics. The essen- tial difference between Euclidean geometry and a grid geometry is that in the former there is "infinite precision" whereas in the latter there is only "finite precision". We define properties for grid geometries which are analogous to the straightness property and its consequences for Euclidean geometries. These grid geometry properties are desirable features to have in line draw- ing algorithms for practical and aesthetic reasons. We design grid geometries which have these properties and for which the path between every pair of grid points is almost straight. We prove that no grid geometry which has these properties can have straighter paths then those we design. This proof uses a fairly deep result from the theory of discrepancies. We develop a very efficient line drawing algorithm based on the grid geometry we design. Joint work with Johan Hastad SYSTEMS SEMINAR, Thursday, February 25, 11 am, SF1101 Dr. William Pugh Cornell University "Incremental Evaluation of Functional Programs" Immediate computation is an interaction style where computed information about a changing object is kept continuously up to date. Performing the calculation from scratch after each change can be too slow; methods which save time by reusing or updating the results of previous computations are known as incremental methods. Incremental algorithms are in most cases substantially harder to derive, debug and maintain than non-incremental algorithms. This difficulty motivates the desire for a system that can incrementally re-evaluate an algorithm that simply specifies how to compute the answer from scratch. Function catching, or memorising, can be used to obtain incremental evalua- tion of functional programs. The amount of incremental behavior that can be extracted from a program depends on the algorithms used, in much the same way as the amount of parallelism that can be extracted from a program depends on the algorithms used. In this talk, I will discuss several issues involved in the efficient implementation of function caching, dis- cuss the kinds of algorithms for which function caching provides incremen- tal behavior, propose appropriate implementations for several abstract data types, and look at the design of an incremental interpreter for a simple imperative language. I will also compare this work to incremental attri- bute grammar evaluation, another scheme for incrementally updating the result of a computation. NUMERICAL ANALYSIS SEMINAR, Friday, February 26, 3 pm, GB220 Professor Kurt Anstreicher Yale School of Management Studies "A Survey of Existing Versions of Karmarkar's Algorithm" -- Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4 (416) 978-4058 BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke