Below are our technical reports which are viewable through the web. The catalogue file contains the same information seen here, plus some reports not available via FTP.

You may also view a Postscript file of the abstracts of the latest papers or see a menu for all abstracts.


NYU Department of Computer Science Technical Reports

tr086-U100
A. Gottlieb, "An Overview of the NYU Ultracomputer Project (Revised)", Oct. 1987

tr221-U101
G. Landau, U. Vishkin, "Efficient Parallel and Serial Approximate String Matching", Feb. 1986

tr222-U102
Y. Maon, B. Schieber, U. Vishkin, "Parallel Ear Decomposition Search (EDS) and ST-Numbering in Graphs", Feb. 1986

tr223-U103
Y. Azar, U. Vishkin, "Tight Comparison Bounds on the Complexity of Parallel Sorting", Feb. 1986

tr242-U108
R. Cole, U. Vishkin, "The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time", Sep. 1986

tr243-U109
R. Cole, C. O'Dunlaing, "Note on the AKS Sorting Network", Sep. 1986

tr485
D. Szyld, O. Widlund, "Variational Analysis of Some Conjugate Gradient Methods", Dec. 1989

tr486-U167
M. Dryja, O. Widlund, "Towards a Unified Theory of Domain Decomposition Algorithms for Elliptic Problems", Dec. 1989

tr489
D. Rennels, E. Schonberg, "A Program Analysis Tool for Evaluating the ADA Compiler Validation Suite", Jan. 1990

tr498
K. Donovan, "Performance of Shared Memory in a Parallel Computer", Mar. 1990

tr503
V. Lanin, D. Shasha, "Tree Locking on Changing Trees", Apr. 1990

tr504-R230
M. Pellegrini, "Stabbing and Ray Shooting in 3-Dimensional Space", May 1990

tr505 M. Overton, "Large-Scale Optimization of Eigenvalues", May 1990

tr506
X. Cai, O. Widlund, "Domain Decomposition Algorithms for Indefinite Elliptic Problems", May 1990

tr507
M. Dryja, O. Widlund, "Multilevel Additive Methods for Elliptic Finite Element Problems", May 1990

tr510
S. Cox, M. Overton, "On the Optimal Design of Columns Against Buckling", June 1990

tr512
R. Cole, "Tight Bounds on the Complexity of the Boyer-Moore Pattern Matching Algorithm", June 1990

tr514
D. Shasha, J. Turek, "Beyond Fail-Stop: Wait-Free Serializability and Resiliency in the Presence of Slow-Down Failures", Sep. 1990

tr517
B. Smith, "Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity", Sep. 1990

tr518
K. Li, "Dag Representation and Optimization of Rewriting", Sep. 1990

tr519
B. Smith, "A Domain Decomposition Algorithm for Elliptic Problems in Three Dimensions", Oct. 1990

tr520
J. Burke, "Stable Perturbations of Nonsymmetric", Oct. 1990

tr523
P. Ouyang, "Execution of Regular DO Loops on Asynchronous Multiprocessors", Oct. 1990

tr529
M. Dryja, "Substructuring Methods for Parabolic Problems", Nov. 1990

tr531
W. Jockush, N. Prabhu, "Cutting a Polytope", Nov. 1990

tr532
G. Bohus, W. Jockush, C. Lee, N. Prabhu, "On Triangulations of the 3-Ball and the Solid Torus", Nov. 1990

tr533
N. Prabhu, "On a Conjecture of Micha Perles", Nov. 1990

tr534
E. Davis, "Physical Idealization as Plausible Inference", Nov. 1990

tr539
R. Cole, O. Zajicek, "The APRAM - The Rounds Complexity Measure and the Explicit Costs of Synchronization", Jan. 1991

tr541
E. Davis, "The Kinematics of Cutting Solid Objects", Jan. 1991

tr542-U170
R. Cytron, J. Lipkis, E. Schonberg, "A Compiler-Assisted Approach to SPMD Execution", Jul. 1990

tr546
R. Cole, O. Zajicek, "An Asynchronous Parallel Algorithm for Undirected Graph Connectivity", Feb. 1991

tr547-R244
G. Gallo, B. Mishra, "Some Constructions in Rings of Differential Polynomials", Mar. 1991

tr548
K. L. Clarkson, R. Cole, R. E. Tarjan, "Randomized Parallel Algorithms for Trapezoidal Diagrams", Mar. 1991

tr549-R245
S. Mallat, W. L. Hwang, "Singularity Detection and Processing with Wavelets", Mar. 1991

tr552 Part 1 Part 2 Part 3 Part 4 Part 5
P. Charles, "A Practical Method for Constructing Efficient LALR(k) Parsers with automatic Error Recovery", Mar. 1991

tr553
I. Rigoutsos, R. Hummel, "Scalable Parallel Geometric Hashing for Hypercube SIMD Architechtures", Jan. 1991

tr554
I. Rgoutsos, R. Hummel, "On a Parallel Implementation of Geometric Hashing on the Connection Machine", Apr. 1991

tr555
K. Laufer, "Comparing Three Approaches to Transformational Programming", Apr. 1991

tr556
F. Henglein, K. Laufer, "Programming with Structures, Functions, and Objects", Apr. 1991

tr557
R. Cole, U. Vishkin, "On the Detection of Robust Curves", Apr. 1991

tr558-R246
G. Koren, B. Mishra, A. Raghunathan, D. Shasha, "On-Line Schedulers for Overloaded Real-Time Systems", May 1991

tr561
R. Sundar, "Amortized Complexity of Data Structures", May 1991

tr562
S. Nepomnyaschikh, "Decomposition and Fictitious Domains Methods for Elliptic Boundary Value Problems", May 1991

tr565
E. Davis, "Lucid Representations", June 1991

tr566
M. Overton, R. Womersley, "Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices", June 1991

tr567
J. Burke, M. Overton, "On the Subdifferentiability of a Matrix Spectrum I: Mathematical Foundations", June 1991

tr568
J. Burke, M. Overton, "On the Subdifferentiability of a Matrix Spectrum II: Subdifferential Formulas", June 1991

tr569-R250
P. Tetali, "Applications and Analysis of Probabilistic Techniques", June 1991

tr570
M. Dryja, O. Widlund, "Additive Schwarz Methods for Elliptic Finite Element Problems in Three Dimensions", June 1991

tr571
F. Gasperoni, U. Schwiegelshohn, "Efficient Algorithms for Cyclic Scheduling", July 1991

tr572
G. Koren, D. Shasha, "An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems", July 1991

tr573
R. Cole, A. Raghunathan, "Online Algorithms for Finger Searching", Aug. 1991

tr574
R. Cole, O. Zajicek, "The Expected Advantage of Asynchrony", Sep. 1991

tr579
J. Burke, M. Overton, "Differential Properties of Eigenvalues", Sep. 1991

tr580
L. Pavarino, "An Additive Schwarz Method for the P-Version Finite Element Method", Sep. 1991

tr581
O. Widlund, "Some Schwarz Methods for Symmetric and Nonsymmetric Elliptic Problems", Sep. 1991

tr582
X. Zhang, "Multilevel Additive Schwarz Methods", Sep. 1991

tr583
X. Zhang, "Domain Decomposition Algorithms for the Biharmonic Dirichlet Problem", Sep. 1991

tr584
X. Zhang, "Studies in Domain Decomoposition: Multilevel Methods and the Biharmonic Dirichlet Problem", Sep. 1991

tr585
M. Hind, "Efficient Loop-Level Parallelishm in ADA", Sep. 1991

tr586
J. Haeberly, "On Shape Optimizing the Ratio of the First Two Eigenvalues of the Laplacian", Oct. 1991

tr587
C. Chang, R. Paige, "New Theoretical and Computational Results for Regular Languages", Oct. 1991

tr588-R255
B. Bederson, R. Wallace, E. Schwartz, "A Miniaturized Active Vision System", Nov. 1991

tr589-R256
R. Wallace, P. Ong, B. Bederson, E. Schwartz, "Space Variant Image Processing", Nov. 1991

tr590
E. Davis, "Axiomating Qualitative Process Theory", Nov. 1991

tr595
X.-C. Cai, O. Widlund, "Multiplicative Schwarz Algorithms for Some Nonsymmetric and Indefinite Problems", Feb. 1992

tr597
G. Park, "Semantic Analyses for Storage Management Optimizations in Functional Language Implementations", Feb. 1992

tr601-R264
B. Bederson, R. Wallace, E. Schwartz, "A Miniature Pan-Tilt Actuator: The Sperical Pointing Motor", Apr. 1992

tr602
J. Cai, X. Han, R. Tarjan, "An $O(m$log$n)$-Time Algorithm for the Maximal Planar Subgraph Problem", Apr. 1992

tr603
J. Cai, "Counting Embeddings of Planar Graphs Using DFS Trees", Apr. 1992

tr604
J. Cai, R. Paige, R. Tajan, "More Efficient Bottom-Up Mult-Pattern Matching in Trees", Apr. 1992

tr606
M. Dryja, O. Widlund, "Domain Decomposition Algorithms with Small Overlap", May 1992

tr607
A. Greenbaum, L. Trefethen, "GMRES/CR and Arnoldi/Lanczos as Matrix Approximation Problems", May 1992

tr608
A. Greenbaum, Z. Strakos, "Matrices that Generate the Same Krylov Residual Spaces", May 1992

tr609
J. Cai, R. Paige, "Multiset Discrimination - A Method for Implementing Programming Language Systems without Hashing", June 1992

tr610
V. Averbukh, S. Figueroa, T. Schlick, "HESFCN - A Fortran package of Hessian Subroutines for Testing Nonlinear Optimization Software", June 1992

tr611-R266 Part 1 Part 2
B. Bederson, "Miniature Space-Variant Active Vision System: Cortex-I", July 1992

tr612-R267
D. Karron, J. Cox, B. Mishra, "The Spiderweb Algorithm for Surface Construction from Medical Volume Data: Geometric Properties of its Surface", July 1992

tr614
L. Pavarino, "Some Schwarz Algorithms for the P-Version Finite Element Method", Sep. 1992

tr615
M. Dryja, O. Widlund, "Some Recent Results on Schwarz Type Domain Decomposition Algorithms", Sep. 1992

tr616
L. Pavarino, "Domain Decomposition Algorithms for the P-Version Finite Element Method for Elliptic Problems", Sep. 1992

tr619
S. Mallat, Z. Zhang, "Matching Pursuits with Time-Frequency Dictionaries", Rev. Aug. 1993

tr620
T.-R. Chuang, B. Goldberg, "Backward Analysis for Higher-Order Functions Using Inverse Images", Nov. 1992

tr621
F. Tsai, "Statistical Approach to Affine Invariant Matching with Line Features", Nov. 1992

tr622 Part 1 Part 2
K. Laufer, "Polymorphic Type Inference and Abstract Data Types", Dec. 1992

tr623
J. Cullum, A. Greenbaum, "Residual Relationships within Three Pairs of Iterative Algorithms for Solving $Ax - b$", Feb. 1993

tr624
J. Haeberly, M. Overton, "A Hybrid Algorithm for Optimizing Eigenvalues of Symmetric Definite Pencils", Feb. 1993

tr625
F. Tsai, "Using Line Invariants for Object Recognition by Geometric Hasing", Feb. 1993

tr626
M. Dryja, O. Widlund, "Schwarz Methods of Neumann-Neumann Type for Three-Dimensional Elliptic Finite Element Problems", Mar. 1993

tr627
M. Overton, R. Womersly, "Second Derivatives for Optimizing Eigenvalues of Symmetric Matrices", Mar. 1993

tr628
G. Gallo, B. Mishra, "The Complexity of Resolvent Resolved", Mar. 1993

tr629
M. Sarkis, "Two-Level Schwarz Methods for Nonconforming Finite Elements and Discontinuous Coefficients", Mar. 1993

tr630
P. Agarwal, "The Cell Programming Language", Mar. 1993

tr631
M. Overton, X. Ye, "Towards Second-Order Methods for Structured Nonsmooth Optimization", Apr. 1993

tr632
Mutukrishnan, K. Palem, "Highly Efficient Dictionary Matching in Parallel", Apr. 1993

tr633
R. Wallace, P. Ong, B. Bederson, E. Schwartz, "Space Variant Image Processing", Apr. 1993

tr634
R. Wallace, "Miniature Direct-Drive Rotary Actuators", Apr. 1993

tr635
J. Cai, "A Language for Semantic Analysis", May 1993

tr636
R. Wallace, B. Bederson, E. Schwartz, "Voice-Bandwidth Visual Communication Through Logmaps: The Telecortex", May 1993

tr637
E. Davis, "Knowledge Preconditions for Plans", May 1993

tr638
M. Dryja, B. Smith, O. Widlund, "Schwarz Analysis of Iterative Substructuring Algorithms for Elliptic Problems in Three Dimensions", May 1993

tr639
G. Koren, D. Shasha, "Competitive Algorithms and Lower Bounds for On-Line Scheduling of Multiprocessor Real-Time Systems", June 1993

tr640
F. Tsai, "A Probabilistic Approach to Geometric Hashing Using Line Features", June 1993

tr641
W. Hwang, S. Mallat, "Chacterization of Self-Similar with Wavelet Maxima", Aug. 1993

tr643
B. Mishra, M. Antoniotti, "ED I: NYU Educational Robot Design and Evaluation", Aug. 1993

tr644 Part 1 Part 2 Part 3
T.-R. Chuang, "New Techniques for the Analysis and Implementation of Functional Programs", Aug. 1993

tr645
A. Greenbaum, "Norms of Functions of Matrices", Aug. 1993

tr646
B. Mishra, "Bidirectional Edges Problem, Part I: A Simple Algorithm", Sep. 1993

tr647
B. Mishra, "Bidirectional Edges Problem, Part II: An Efficient Algorithm", Sep. 1993

tr648
L. Pavarino, O. Widlund, "Iterative Substructuring Methods for Spectral Elements in Three Dimensions", Sep. 1993

tr650
B. Mishra, "A Survey of Computational Differential Algebra", Oct. 1993

tr651
R. Wallace, "Miniature Direct Drive Rotary Actuators II: Eye, Finger, and Leg", Nov. 1993

tr652
D. Max, R. Wallace, "Feedback Control of Miniature Direct Drive Devices", Nov. 1993

tr653
B. Mishra, M. Antoniotti, F. Hansen, R. Wallace, "NYU Educational Robotics Project: A Pedagogic Overview", Nov. 1993

tr654
H. Chen, "Multilevel Schwarz Methods with Partial Refinement", Mar. 1994

tr655
C. Yao, B. Goldberg, "Pscheme: Extending Continuations to Express Control and Synchronization in a Parallel LISP", Mar. 1994

tr657
G. Davis, S. Mallat, Z. Zhang, "Adaptive Time-Frequency Approximations with Matching Pursuits", Mar. 1994

tr658 Figures
J. Maddocks, M. Overton, "Stability Theory for Dissipatively Perturbed Hamiltonian Systems", Mar. 1994

tr659
F. Alizadeh, J. P. Haeberly, M. Overton, "A New Primal-Dual Interior-Point Method for Semidefinite Programming", Mar. 1994

tr660
J. P. Haeberly, M. Overton, "Optimizing Eigenvalues of Symmetric Definite Pencils", Mar. 1994

tr661
L. Pavarino, O. Widlund, "A Polylogarithmic Bound for an Iterative Substructuring Method for Spectral Elements in Three Dimensions", Mar. 1994

tr662
M. Dryja, M. Sarkis, O. Widlund, "Multilevel Schwarz Methods for Elliptic Problems with Discontinuous Coefficients in Three Dimensions", Mar. 1994

tr663
L. Pavarino, O. Widlund, "Iterative Substructuring Methods for Spectral Elements: Problems in Three Dimensions Based on Numerical Quadrature", May 1994

tr664
M. Antoniotti, "Conceptual and Pragmatic Tools for Design and Control of Manufacturing Systems (Petrinets and Ramadge-Wonham Discrete Event Systems)"

tr665
S. Gomory, R. Wallace, "Cursor Stereo", May 1994

tr666
E. Davis, "Branching Continuous Time and the Semantics of Continuous Action", Jul. 1994

tr667
C. Yao, "Representing Control in Parallel Applicative Programing", Sep. 1994

tr668
M. Ebner, R. Wallace, "A Direct-Drive Hand: Design, Modeling and Control", Jun. 1994

tr669
R. Wallace, J. Selig, "Scaling Direct Drive Robots", Aug. 1994

tr670
J. Choi, J. Sellen, C.K. Yap, "Approximate Euclidean Shortest Path in 3-Space" Sep. 1994

tr671
M.S. Martins, "Schwarz Preconditioners for Elliptic Problems with Discontinuous Coefficients Using Conforming and Non-Conforming Elements", Sep. 1994

tr672
J. Sellen, "Planning Paths of Minimal Curvature", Oct. 1994

Abstract: We consider the problem of planning curvature constrained paths amidst polygonal obstacles, connecting given start and target configurations. Let the critical curvature Rc be the minimal curvature for which a constrained path exists. We describe an algorithm, which approximates the critical curvature and finds a corresponding path. Further, we give an efficient decision procedure to determine if there exists a path satisfying a given curvature constraint R, with running time polynomial in |R-Rc|/R.

tr673
S. M. Sokolov, D. P. Max, R. S. Wallace, "Simple Multi Function Vision System for 3D Data Acquisition", Oct. 1994

Abstract: We have developed a simple multi function vision system for 3D data acquisition for a wide range of applications in robotics and automation. The system uses one CCD video camera and an active directed laser light source based on a direct drive spherical pointing motor (SPM). The anatomy of the system and algorithms used are described. System calibration methods and measurements of accuracy of the outputs are presented. A list of applications is shown.

tr674
M. Antoniotti, B. Mishra, "Automatic Synthesis Algorithms for Supervisory Controllers (Preliminary Report)", Nov. 1994

Abstract: In this paper we describe our experience with a prototype system capable of synthesizing "Supervisor Controller Programs" based largely on the theory of discrete event systems (DES) first proposed by Ramadge and Wonham. We augment the theory by also allowing continuous time trajectories modeling transitions between events. We illustrate our approach by an example, - the discrete control of a walking machine - which poses some challenges on the applicability of the theory and finally, discuss some possible solutions.

Notes: Appeared in IEEE Proceedings of the Fourth International Conference on Computer Integrated Manufacturing and Automation Technology, Troy, NY, Oct. 1994

tr675
M. Antoniotti, B. Mishra, "Discrete Event Models + Temporal Logic = Supervisory Controller: Automatic Synthesis of Locomotion Controllers", Nov. 1994

Abstract: In this paper, we address the problem of the synthesis of controller programs for a variety of robotics and manufacturing tasks. The problem we choose for test and illustrative purposes is the standard ``Walking Machine Problem,'' a representative instance of a real "hybrid" problem with both logical/discrete and continuous properties and strong mutual influence without any reasonable separation. We aim to produce a ``compiler technology'' for this class of problems in a manner analogous to the development of the so-called ``Silicon Compilers'' for the VLSI technology. To cope with the difficulties inherent to the problem, we resort to a novel approach that combines many key ideas from a variety of disciplines: namely, ``Discrete Event Supervisory Systems'', Petri Nets approaches and ``Temporal Logic''.

Notes: Will appear in the 1995 IEEE International Conference on Robotics and Automation, Nagoya, Japan

tr676
A. Klawonn, "An Optimal Preconditioner for a Class of Saddle Point Problems with a Penalty Term", Dec. 1994

Abstract: Iterative methods are considered for a class of saddle point problems with a penalty term arising from finite element discretizations of certain elliptic problems. An optimal preconditioner which is independent of the and the penalty parameter is constructed. This approach is then used to design an iterative method with a convergence rate independent of the Lam\'{e} parameters occuring in the equations of linear elasticity.

Please see revised version tr683.

tr677
A. Knyazev, "New Estimates for Ritz Vectors", Dec. 1994

Abstract: The followiing estimate for the Rayleigh--Ritz method is proved: $$ | \tilde \lambda - \lambda | |( \tilde u , u )| \le { \| A \tilde u - \tilde \lambda \tilde u \| } \sin \angle \{ u ; \tilde U \}, \ \| u \| =1. $$ Here $A$ is a bounded self-adjoint operator in a real Hilbert/euclidian space, $\{ \lambda, u \}$ one of its eigenpairs, $\tilde U$ a trial subspace for the Rayleigh--Ritz method, and $\{ \tilde \lambda, \tilde u \}$ a Ritz pair. %$\| u \| = \| \tilde u \| = 1.$ This inequality makes it possible to analyze the fine structure of the error of the Rayleigh--Ritz method, in particular, it shows that $ |( \tilde u , u )| \le C \epsilon^2, $ if an eigenvector $u$ is close to the trial subspace with accuracy $\epsilon$ and a Ritz vector $\tilde u$ is an $\epsilon$ approximation to another eigenvector, with a different eigenvalue. Generalizations of the estimate to the cases of eigenspaces and invariant subspaces are suggested, and estimates of approximation of eigenspaces and invariant subspaces are proved.

tr678 Part 1 Part 2 Part 3 Part 4
A. Gueziec, R. Hummel, "The Wrapper Algorithm for Surface Extraction in Volumetric Data", Dec. 1994

Abstract: Beginning with digitized volumetric data, we wish to rapidly and efficiently extract and represent surfaces defined as isosurfaces in the interpolated data. The Marching Cubes algorithm is a standard approach to this problem. We instead perform a decomposition of each 8-cell associated with a voxel into five tetrahedra, as in the Payne-Toga algorithm. Following the ideas of Kalvin, Thirion et al., and using essentially the same algorithm as Doi and Koide, we guarantee the resulting surface representation to be closed and oriented, defined by a valid triangulation of the surface of the body, which in turn is presented as a collection of tetrahedra, some of which are only partly filled. The surface is extracted as a collection of closed triangles, where each triangle is an oriented closed curve contained within a single tetrahedron. The entire surface is ``wrapped'' by the collection of triangles, using especially efficient data structures. The representation is similar to the homology theory that uses simplices embedded in a manifold to define a closed curve within each tetrahedron.

From the triangles that comprise the wrapping of the surface, we give methods to evaluate surface curvatures and principal directions at each vertex, whenever these quantities are defined. We further present a fast method for rendering and approximating the surface. The triangles form a graph structure, which is very efficiently encoded, whose nodes are the triangles and whose edges are the common edges joining adjacent triangles. We can thus identify each surface using a connected component labelling algorithm applied to the graph.

This provides a highly parallelizable approach to boundary surface representation, providing an efficiently and compact surface representation. The wrapper algorithm has been used to extract surfaces of the cranium from CT-scans and cortical surfaces from MR-scans at full resolution.

Key words: B-rep, boundary representation, Marching Cubes, tetrahedral decomposition, homology theory, surface curvature.

tr679
C. Yap, "Report on NSF Workshop on Manufacturing and Computational Geometry", Jan. 1995

Abstract: This is a summary of the NSF Workshop on Manufacturing and Computational Geometry, held at the Courant Institute of Mathematical Sciences, New York University, on April 1-2, 1994. The meeting brought together about 30 participants from both the manufacturing and the computational geometry communities for the purposes of discussing current trends in the two communities, identifying areas of mutual interest, and proposing future joint activities.

tr680
B. Mishra, "Grasp Metrics: Optimality and Complexity", Jan. 1995

Abstract: In this paper, we discuss and compare various metrics for goodness of a grasp. We study the relations and trade-offs among the goodness of a grasp, geometry of the grasped object, number of fingers and the computational complexity of the grasp-synthesis algorithms. The results here employ the techniques from convexity theory first introduced by the author and his colleagues.

tr681
F. Alizadeh, J. Haeberly, M. Overton, "Complementarity and Nondegeneracy in Semidefinite Programming", Mar. 1995

Abstract: Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutions $X$ and $Z$. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks of $X$ and $Z$ which are consistent with the nondegeneracy conditions.

tr682
K. Andersen, E. Christiansen, M. Overton, "Computing Limit Loads by Minimizing a Sum of Norms", Apr. 1995

Abstract: We consider the problem of computing the collapse state in limit analysis for a solid with a quadratic yield condition, such as, for example, the Mises condition. After discretization with the finite element method, using divergence-free elements for the plastic flow, the kinematic formulation turns into the problem of minimizing a sum of Euclidean vector norms, subject to a single linear constraint. This is a nonsmooth minimization problem, since many of the norms in the sum may vanish at the optimal point. However, efficient solution algorithms for this particular convex optimization problem have recently been developed.

The method is applied to test problems in limit analysis in two different plane models: plane strain and plates. In the first case more than 80 percent of the terms in the sum are zero in the optimal solution, causing severe ill-conditioning. In the last case all terms are nonzero. In both cases the algorithm works very well, and we solve problems which are larger by at least an order of magnitude than previously reported. The relative accuracy for the discrete problems, measured by duality gap and feasibility, is typically of the order 1.0E-8. The discretization error, due to the finite grid, depends on the nature of the solution. In the applications reported here it ranges from 1.0E-5 to 1.0E-2.

Keywords: Limit analysis, plasticity, finite element method, nonsmooth optimization.

tr683
A. Klawonn, "An Optimal Preconditioner for a Class of Saddle Point Problems with a Penalty Term, Part II: General Theory", Apr. 1995

Abstract: Iterative methods are considered for saddle point problems with penalty term. A positive definite preconditioner is constructed and it is proved that the condition number of the preconditioned system can be made independent of the discretization and the penalty parameters. Examples include the pure displacement problem in linear elasticity, the Timoshenko beam, and the Mindlin-Reissner plate.

Key words: Saddle point problems, penalty term, nearly incompressible materials, Timoshenko, Mindlin-Reissner, preconditioned conjugate residual method, multilevel, domain decomposition.

Please note: This report is a revised version of tr676.

tr684
A. Siegel, "On Universal Classes of Extremely Random Constant Time Hash Functions and their Time-space Tradeoff", Apr. 1995

Abstract: A family of functions F that map [0,n]->[0,n], is said to be h-wise independent if any h points in [0,n] have an image, for randomly selected f in F, that is uniformly distributed. This paper gives both probabilistic and explicit randomized constructions of (n**epsilon)-wise independent functions, for epsilon<1, that can be evaluated in constant time for the standard random access model of computation. Simple extensions give comparable behavior for larger domains. As a consequence, many probabilistic algorithms can for the first time be shown to achieve their expected asymptotic performance for a feasible model of computation.

This paper also establishes a tight tradeoff in the number of random seeds that must be precomputed for a random function that runs in time T and is h-wise independent.

tr685
A. Siegel, "Toward a Usable Theory of Chernoff Bounds for Heterogeneous and Partially Dependent Random Variables", Apr. 1995

Abstract: Let X be a sum of real valued random variables and have a bounded mean E[X]. The generic Chernoff-Hoeffding estimate for large deviations of X is: P{X-E[X]>=a}<=min_{y>=0}exp(-y(a+E[X]))E[exp(y X)], which applies with a>=0 to random variables with very small tails. At issue is how to use this method to attain sharp and useful estimates. We present a number of Chernoff-Hoeffding bounds for sums of random variables that may have a variety of dependent relationships and that may be heterogeneously distributed.

tr686
J. Schmidt, A. Siegel, "Double Hashing is Computable and Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing and virtually any reasonable generalization of double hashing that has an expected probe count of 1/(1-alpha) + epsilon for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1 and epsilon > 0. This performance is within epsilon of optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of partial items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

tr687
A. Siegel, J. Schmidt, "Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing, uniform hashing and virtually anyreasonable generalization of double hashing that has an expected probe count of 1/(1-alpha)+O(1/n) for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1. This performance is optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of local items already inserted into the hash table, and from a very sharp analysis of the underlying stochasticstructures formed by colliding items.

Analogous bounds are attained for the expected r-th moment of the probe count, or any fixed r, and linear probing is also shown to achieve a performance with universal hash functions that is equivalent to the fully random case.

tr688
A. Muravitsky, "On the First Degree Entailment of Two 3-Valued Logics", May 1995

Abstract: We note first that the first degree entailment of {\L}ukasiewicz's 3-valued logic and a 3-valued logic that is extracted of Belnap's 4-valued logic is the same. Then, we give an axiomatization of that entailment as the calculus E_{fde} + A&-A->B\/-B, where E_{fde} is the first degree entailment of Anderson-Belnap's logic E of relevance and necessity.

tr689
A. Muravitsky, "Knowledge Representation as Domains", May 1995

Abstract: This is a continuing attempt in a series of papers [ knowledge.ps, inform.ps, frame.ps ] to show how computer-represented knowledge can be arranged as elements of an effectively represented semantic domain in the sense of [C.A.Gunter and D.S.Scott, Semantic Domains, in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. B, pp. 635--674]. We present a direct deductive description of the domain, which was defined semantically in [ knowledge.ps ], via the Scott's notion of information system. Also, the internal structure of the continuous ampliative operations coordinated with the domain's effective basis is established. Though we always remain in the paradigm of the toleration of contradictory information described in [N.D.Belnap, A Useful Four-Valued Logic: How a Computer Should Think, in: A.R.Anderson, N.D.Belnap, and J.M.Dunn, Entailment: the Logic of Relevance and Necessity, Vol. 2, Princeton Univ. Press, 1992], the approach in question could be extended to include domains for consistency knowledge bases.

tr690
A. Muravitsky, "A Framework for Knowledge-Based Systems", May 1995

Abstract: The paper continues the theme of [ knowledge.ps ]. We differentiate between our approach to knowledge representation and that of others by expressing the following Working Hypothesis: Knowledge is a data type, and knowledge revision is accomplished by continuous operations on it, which are coordinated with its effective basis. Staying in the limits of Belnap's paradigm of the admittance of contradictory information into the computer's memory, our purpose in this paper is to reduce as much as possible all the computable processes needed for modifing the current state of the computer's knowledge and describe conditions for possible maneuvering. In particular, we solve some problems of decidability concerning operations on the minimal states, which are regarded as natural knowledge transformers. We show, also, how to express those operations in lattice theory terms that leads to the simplification of their computation on the lattice of minimal states. The problem of backtracking in the presented context is considered as well.

tr691
A. Muravitsky, "Some Knowledge Transformers: Infons and Constraints", May 1995

Abstract: The goal of this paper is twofold. First, it is to present a general scheme within which information is supposed to turn into the computer-represented knowledge and, second, to define two natural kinds of transfomers of this knowledge which this scheme thrusts us into considering.

tr692
Y. Kaluzhny, A. Muravitsky, "A Knowledge Representation Based on the Belnap's Four-Valued Logic", May 1995

Abstract: We treat knowledge from a computer-oriented point of view, considering it as a kind of data type. An axiomatic approach to the notion of data type undertaken by Dana Scott in [D.S.Scott, Outline of a Mathematical Theory of Computation, in: Proceedings of Princeton Conference on Information Science, 1971, pp. 169--176], is explored to find entities suitable for representation techniques. At the same time, we stay in Belnap's paradigm of the toleration of inconsistency. We propose a representation of knowledge (possible with contradictions) in simple propositional language, and we show how such knowledge can be maintained and how it should be transformed on receipt of new information. In this transformation, the key role is played by Scott's continuity rather than consistency.

tr693
A. Muravitsky, "A Perspective of New Foundations for Knowledge Maintenance Systems: Research Program", May 1995

Abstract: We propose to provide new mathematical foundations for the design of knowledge-based systems. The underlying idea is that the knowledge which the computer (``artificial agent'') operates with is considered as a kind of abstract data type. In this context, a relation of approximation arises in a natural way when one imagines the computer as operating in a changing information environment (``information flow''). This notion of pproximation can be studied using the techniques that have been developed for domain theory in the context of denotational semantics of programming languages.

tr694
A. Muravitsky, "Logic of Information Knowledge", May 1995 (see tr #691)

Abstract: We share with some philosophers the view that a state of knowledge, being a part of the real world, can bring contradiction into it. Such an ontological reading of knowledge is very important when one deals with information knowledge, which arises as the content of the computer's memory when the computer is placed into changeable information environment ("information flow"), and "must" be able to tolerate any (not excluding contradictions) from the computer's users. Continuing research begun in [KM 93], we consider in length one kind of Scott-continuous operations introduced there. Each such operation [A->B](x), where A and B are formulas in a propositional language, called a rule, moves the computer to a "minimal" state of knowledge, in which B is true, if in a current state A is true. Note that the notion of rule is used here in an information-transforming sense, rather than in the ordinary truth-sound sense. We distinguish between global and local rules and show that these notions are decidable. Also, we define a modal epistemic logic as a tool for the prediction of possible evolution of the system's knowledge and establish decidability of this logic.

tr694
A. Kheyfits, "Dirichlet Problem for the Schrodinger Operator in a Half-space with Boundary Data of Arbitrary Growth at Infinity", May 1995

Abstract: We consider the Dirichlet problem for the Schrodinger operator in a half-space with boundary data having an arbitrary growth at infinity. A solution is constructed as the generalized Poisson integral. Uniqueness of the solution is investigated too.