An algorithm for solving sparse Nonlinear Least Squares problems

We introduce a new method for solving Nonlinear Least Squares problems when the Jacobian matrix of the system is large and sparse. The main features of the new method are the following:

1. The Gauss-Newton equation is “partially” solved at each iteration using a preconditioned Conjugate Gradient algorithm.
2. The new point is obtained using a two-dimensional trust region scheme, similar to the one introduced by Bulteau and Vial.

We prove global and local convergence results and we present some numerical experiments.     

A computational approach to implicit entities and events in text and discourse

In this paper we will focus on the notion of “implicit” or lexically unexpressed linguistic elements that are nonetheless necessary for a complete semantic interpretation of a text. We refer to “entities” and “events” because the recovery of the implicit material may affect all the modules of a system for semantic processing, from the grammatically guided components to the inferential and reasoning ones. Reference to the system GETARUNS offers one possible implementation of the algorithms and procedures needed to cope with the problem and enables us to deal with all the spectrum of phenomena. The paper will address at first the following three types of “implicit” entities and events:

the grammatical ones, as suggested by a linguistic theories like LFG or similar generative theories;

the semantic ones suggested in the FrameNet project, i.e. CNI, DNI, INI;

the pragmatic ones: here we will present a theory and an implementation for the recovery of implicit entities and events of (non-) standard implicatures.

In particular we will show how the use of commonsense knowledge may fruitfully contribute to find relevant implied meanings. Last Implicit Entity only touched on, though for lack of space, is the Subject of Point of View, which is computed by Semantic Informational Structure and contributes the intended entity from whose point of view a given subjective statement is expressed.     

Kernel language KLND

This paper presents a kernel language KLND on the basis of analysing the kernel languagerequirements of new generation computer systems. These requirements are: the ability ofknow-ledge processing, the parallelism, the elegant mathematical properties of the comput-ation model which is appropriate for working as the basis of the novel architecture design, andthe suitability for writing large scale softwares. The main features of KLND are as follows: 1. several new language concepts. 2. the modularity, 3. the unification of logical and functional programming styles, 4. the exploitation of the parallelism. 5. the introduction of the type concept, 6. the introduction of the storage concept.     

Efficiently extendible mappings for balanced data distribution

In data storage applications, a large collection of consecutively numbered data “buckets” are often mapped to a relatively small collection of consecutively numbered storage “bins.” For example, in parallel database applications, buckets correspond to hash buckets of data and bins correspond to database nodes. In disk array applications, buckets correspond to logical tracks and bins correspond to physical disks in an array. Measures of the “goodness” of a mapping method include:

1. Thetime (number of operations) needed to compute the mapping.
2. Thestorage needed to store a representation of the mapping.
3. Thebalance of the mapping, i.e., the extent to which all bins receive the same number of buckets.
4. The cost ofrelocation, that is, the number of buckets that must be relocated to a new bin if a new mapping is needed due to an expansion of the number of bins or the number of buckets.

One contribution of this paper is to give a new mapping method, theInterval-Round-Robin (IRR) method. The IRR method has optimal balance and relocation cost, and its time complexity and storage requirements compare favorably with known methods. Specifically, ifm is the number of times that the number of bins and/or buckets has increased, then the time complexity isO(logm) and the storage isO(m ²). Another contribution of the paper is to identify the concept of ahistory-independent mapping, meaning informally that the mapping does not “remember” the past history of expansions to the number of buckets and bins, but only the current number of buckets and bins. Thus, such mappings require very little information to be stored. Assuming that balance and relocation are optimal, we prove that history-independent mappings are possible if the number of buckets is fixed (so only the number of bins can increase), but not possible if the number of bins and buckets can both increase.     

Inventive machine: Second generation

Inventive Machine project is the matter of discussion. The project aims to develop a family of AI systems for intelligent support of all stages of engineering design. Peculiarities of the IM project:

1. deep and comprehensive knowledge base — the theory of inventive problem solving (TIPS)
2. solving complex problems at the level of inventions
3. application in any area of engineering
4. structural prediction of engineering system development

The systems of the second generation are described in detail     

An inference structure for process feedback: technique and implementation

This paper presents an automatic technique for making simple inferences about the stages in a software production process, discusses implementation of the technique, and validates the technique using defect data from several software development projects. The technique represents an approach to automate process feedback that may be based on either experience and common sense or historical data. Specifically, we present

1. A software defect classification scheme that relates defects to process stages. As an example of such a scheme, we describe ‘orthogonal defect classification’, which associates types of defects with stages, such as high-level design, low-level design, code, and system test. These associations are summarized in a ‘principal association’ table, which serves as a model for the production process.
2. Rules that provide simple in-process feedback about a process stage based on the defects associated with that stage. We discuss how inferences can be made, with and without historical information for the process, and illustrate application of the inference technique to the software production process.
3. An implementation of the rules using a statistical programming language.

Finally, we consider the technique in the software production context as a particular case of a general technique that makes use of both human judgment and historical data, and discuss extensions.     

On the sequential nature of interprocedural program-analysis problems

In this paper, we study two interprocedural program-analysis problems—interprocedural slicing and interprocedural dataflow analysis— and present the following results:

? Interprocedural slicing is log-space complete forP.

? The problem of obtaining “meet-over-all-valid-paths” solutions to interprocedural versions of distributive dataflow-analysis problems isP-hard.

? Obtaining “meet-over-all-valid-paths” solutions to interprocedural versions of distributive dataflow-analysis problems that involve finite sets of dataflow facts (such as the classical “gen/kill” problems) is log-space complete forP.

These results provide evidence that there do not exist fast (N?-class) parallel algorithms for interprocedural slicing and precise interprocedural dataflow analysis (unlessP =N?). That is, it is unlikely that there are algorithms for interprocedural slicing and precise interprocedural dataflow analysis for which the number of processors is bounded by a polynomial in the size of the input, and whose running time is bounded by a polynomial in the logarithm of the size of the input. This suggests that there are limitations on the ability to use parallelism to overcome compiler bottlenecks due to expensive interprocedural-analysis computations.     

Enhanced qualitative physical reasoning system: Qupras

There are many expert systems that use experimental knowledge for diagnostic analysis and design. However, there are two problems for systems using only experiential knowledge:

1. unexpected problems cannot be solved and
2. acquiring experiential knowledge from human experts is difficult.

To solve these problems, general principles or basic knowledge must be added to expert systems in addition to the experimental knowledge. In response, we previously proposed Qupras (Qualitative physical reasoning system) as a framework for basic knowledge. This system has two knowledge representations, one related to physical laws and the other to objects. By using this knowledge, Qupras reasons about the relations among physical objects, and predicts the next state of a physical phenomenon. Recently, we have improved some of Qupras’ features, and this pater desctibes the following main enhancements:

1. inheritance for representation of objects,
2. new primitive representations to describe discontinuous change, and
3. control features for effective reasoning.

     

Unternehmensweites Berechtigungsmanagement

The central coordination of access control management is crucial especially for companies that are engaged in cooperative processes with other companies. Most critical is to respect the security needs that arise with the “opening“ towards other partners.

• The central coordination of access control is indispensable in order to protect the company’s resources.
• If access control management is to be oriented directly towards the corporate goals in contrast to a merely technical view there is a need for extended concepts — like role based access control (RBAC).
• The first software products that make use of the RBAC-concept for a centrally coordinated access control management are available and can be used in practice.

     

High-speed tools for Global Information Management I. Information processing and retrieval

The general specifications and design for a High-Speed General Information Management System, HSGIMS, to serve as the basis for a Global Information Network are given. Some of the key specifications that have been confirmed in experiments with a prototype of the HSGIMS are:

1. Information (or data) and Question-type (or logical data) independence.
2. Very small bounded search times that are independent of the amount of information that is managed and can be computed exactly.
3. A fool-proof security system that can be used to protect databases against viruses and can also be easily invoked to deny unauthorized access by users.
4. Efficient use of all storage and communications resources.

     

Specification and refinement of networks of asynchronously communicating agents using the assumption/commitment paradigm

This paper presents an assumption/commitment specification technique and a refinement calculus for networks of agents communicating asynchronously via unbounded FIFO channels in the tradition of Kahn.

We define two types of assumption/commitment specifications, namely simple and general specifications.

It is shown that semantically, any deterministic agent can be uniquely characterized by a simple specification, and any nondeterministic agent can be uniquely characterized by a general specification.

We define two sets of refinement rules, one for simple specifications and one for general specifications. The rules are Hoare-logic inspired. In particular the feedback rules employ invariants in the style of a traditional while-rule.

Both sets of rules have been proved to be sound and also (semantic) relative complete.

Conversion rules allow the two logics to be combined. This means that general specifications and the rules for general specifications have to be introduced only at the point in a system development where they are really needed.

     

Experiences with software specification and verification using LP,the Larch proof assistant

We sketch a method for deduction-oriented software and system development. The method incorporates formal machine-supported specification and verification as activities in software and systems development. We describe experiences in applying this method. These experiences have been gained by using the LP, the Larch proof assistant, as a tool for a number of small and medium size case studies for the formal development of software and systems. LP is used for the verification of the development steps. These case studies include

? quicksort

? the majority vote problem

? code generation by a compiler and its correctness

? an interactive queue and its refinement into a network.

The developments range over levels of requirement specifications, designs and abstract implementations. The main issues are questions of a development method and how to make good use of a formal tool like LP in a goal-directed way within the development. We further discuss the value of advanced specification techniques, most of which are deliberately not supported by LP and its notation, and their significance in development, Furthermore, we discuss issues of enhancement of a support system like LP and the value and the practicability of using formal techniques such as specification and verification in the development process in practice.     

Average time behavior of distributive sorting algorithms

In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX ₁, ...,X _n drawn from a densityf onR ¹. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n ² is nonincreasing andg is independent off), the following is shown:

1. Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
2. Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .

No additional restrictions are put onf.     

Optimal parallel algorithms for rectilinear link-distance problems

We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute:

1. Minimum réctilinear link paths, or shortest paths in theL ₁ metric from any point inP to all vertices ofP.
2. Minimum rectilinear link paths from any segment insideP to all vertices ofP.
3. The rectilinear window (histogram) partition ofP.
4. Both covering radii and vertex intervals for any diagonal ofP.
5. A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor).

Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which usedO(n logn) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.     

Some computational problems in linear algebra as hard as matrix multiplication

We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are:

KER _n : Compute a basis of the kernel for a givenn×n-matrix,

OGB _n : Find an invertible matrix that transforms a given symmetricn×n-matrix (quadratic form) into diagonal form,

SPR _n : Find a sparse representation of a givenn×n-matrix.

     

Channel routing in knock-knee mode: Simplified algorithms and proofs

We give unified and simplified algorithms and proofs for three results on channel routing in knock-knee mode. LetP be a channel routing problem with densityd _max.

1. [Rivest/Baratz/Miller, Preparata/Lipski]. If all nets inP are two-terminal nets thend _max tracks suffice.
2. [Preparata/Sarrafzadeh]. If all nets inP are two- or three-terminal nets then [3d _max/2] tracks suffice.
3. [Sarrafzadeh/Preparata]. 2d _max-1 tracks always suffice.

In all three cases a solution can be found in linear time; this is an improvement in case (b).     

Constant-time hough transform on the processor arrays with reconfigurable bus systems

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

1. The sum ofn bits can be computed in O(1) times on a PARBS with O(n ^1+?) processors for any fixed ?>0.
2. The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n ^2+?) processors for any fixed ?>0.
3. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ^2+?) processors for any fixed ?>0 withp copies of the image pretiled.
4. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ³) processors.

     

Powerful Parallel and Symmetric 3D Thinning Schemes Based on Critical Kernels

The main contribution of the present article consists of new 3D parallel and symmetric thinning schemes which have the following qualities:

They are effective and sound, in the sense that they are guaranteed to preserve topology. This guarantee is obtained thanks to a theorem on critical kernels;

They are powerful, in the sense that they remove more points, in one iteration, than any other symmetric parallel thinning scheme;

They are versatile, as conditions for the preservation of geometrical features (e.g., curve extremities or surface borders) are independent of those accounting for topology preservation;

They are efficient: we provide in this article a small set of masks, acting in the grid ?³, that is sufficient, in addition to the classical simple point test, to straightforwardly implement them.

     

RaumComputer

The RoomComputer is an embedded system and as such offers unprecedented chances to manage buildings. Several RoomComputers can be networked via the Intra-/Internet, which makes it possible to monitor, control, and manage rooms and buildings on a unified worldwide accessible platform, irrespective of any particular local technology. It can be easily installed in any building and gives access to a full set of services. It implements a distributed system, which provides secure and controlled access to services like

1. control of light, heating, ventilation, air and climate
2. communication facilities like unified messaging, telephone, fax, etc.
3. reservation of rooms and required resources
4. localization of persons and equipment within rooms and buildings
5. entrance control (i.e. locking/unlocking doors)
6. organization of maintenance and house keeping, and
7. charging and billing.