Computer Engineering Commons^™

Fast Algorithms For Uncertainty Propagation, And Their Applications To Structural Integrity, Andrzej Pownuk, Jakub Cerveny, Jerald Brady

Departmental Technical Reports (CS)

In many practical situations, we need to know how uncertainty propagates through data processing algorithms, i.e., how the uncertainty in the inputs affects the results of data processing. This problem is important for all types of uncertainty: probabilistic, interval, and fuzzy. From the computational viewpoint, however, this problem is much more complex for interval and fuzzy uncertainty. Therefore, for these types of uncertainty, it is desirable to design faster algorithms.

In this paper, we describe faster algorithms for two practically important situations:

linearization situations, when the approximation errors are small and therefore, the data processing algorithms can be replaced by …

Opportunistic Checkpoint Intervals To Improve System Performance, Sarala Arunagiri, John T. Daly, Patricia J. Teller, Seetharami Seelam, Ron A. Oldfield, Maria Ruiz Varela, Rolf Riesen

Departmental Technical Reports (CS)

The massive scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. For applications that perform periodic checkpoints, the choice of the checkpoint interval, the period between checkpoints, can have a significant impact on the execution time of the application. Finding the optimal checkpoint interval that minimizes the wall clock execution time, has been a subject of research over the last decade. In an environment where there are concurrent applications competing for access to the network and storage resources, in addition to application execution times, contention at these shared resources need to be …

Impact Of Checkpoint Latency On The Optimal Checkpoint Interval And Execution Time, Sarala Arunagiri, Seetharami Seelam, Ron A. Oldfield, Maria Ruiz, Patricia J. Teller, Rolf Riesen

Departmental Technical Reports (CS)

The massive scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. In particular, the standard approach to fault tolerance, application-directed checkpointing, puts an incredible strain on the storage system and the interconnection network. This results in overheads on the appliation that severely impact performance and scalability. The checkpoint overhead can be reduced by decreasing the checkpoint latency, which is the time to write a checkpoint file, or by increasing the checkpoint interval, which is the compute time between writing checkpoint files. However, increasing the checkpoint interval may increase execution time in the …

Towards Fast Algorithms For Processing Type-2 Fuzzy Data: Extending Mendel's Algorithms From Interval-Valued To A More General Case, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

It is known that processing of data under general type-1 fuzzy uncertainty can be reduced to the simplest case -- of interval uncertainty: namely, Zadeh's extension principle is equivalent to level-by-level interval computations applied to alpha-cuts of the corresponding fuzzy numbers.

However, type-1 fuzzy numbers may not be the most adequate way of describing uncertainty, because they require that an expert can describe his or her degree of confidence in a statement by an exact value. In practice, it is more reasonable to expect that the expert estimates his or her degree by using imprecise words from natural language -- …

Everything Is A Matter Of Degree: A New Theoretical Justification Of Zadeh's Principle, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main ideas behind fuzzy logic and its applications is that everything is a matter of degree. We are often accustomed to think that every statement about a physical world is true or false -- that an object is either a particle or a wave, that a person is either young or not, either well or ill -- but in reality, we sometimes encounter intermediate situations. In this paper, we show that the existence of such intermediate situations can be theoretically explained -- by a natural assumption that the real world is cognizable.

Cahsi Year 2 Evaluation Report: Recruiting, Retaining, And Advancing Hispanics In Computing, Heather Thiry, Sarah Hug, Lecia Barker

Departmental Technical Reports (CS)

No abstract provided.

Beyond Intervals: Phase Transitions Lead To More General Ranges, Karen Villaverde, Gilbert Ornelas

Departmental Technical Reports (CS)

One of the main tasks of science and engineering is to use the current values of the physical quantities for predicting the future values of the desired quantities. Due to the (inevitable) measurement inaccuracy, we usually know the current values of the physical quantities with interval uncertainty. Traditionally, it is assumed that all the processes are continuous; as a result, the range of possible values of the future quantities is also known with interval uncertainty. However, in many practical situations (such as phase transitions), the dependence of the future values on the current ones becomes discontinuous. We show that in …

Applications Of 1-D Versions Of Image Referencing Techniques To Hydrology And To Patient Rehabilitation, Roberto Araiza, Martine Ceberio, Naga Suman Kanagala, Vladik Kreinovich, Gang Xiang

Departmental Technical Reports (CS)

In this paper, we consider two seemingly unrelated problems: the hydrology problem of relation between groundwater and surface water, and a problem of identification of human gait in neuro-rehabilitation. It turns out that in both problems, we can efficiently use soft computing-motivated algorithms originally developed for image referencing.

Selecting The Most Representative Sample Is Np-Hard: Need For Expert (Fuzzy) Knowledge, J. Esteban Gamez, Francois Modave, Olga Kosheleva

Departmental Technical Reports (CS)

One of the main applications of fuzzy techniques is to formalize the notions of "typical", "representative", etc.

The main idea behind fuzzy techniques is that they formalize expert knowledge expressed by words from natural language.

In this paper, we show that if we do not use this knowledge, i.e., if we only use the data, then selecting the most representative sample becomes a computationally difficult (NP-hard) problem. Thus, the need to find such samples in reasonable time justifies the use of fuzzy techniques.

Estimating Variance Under Interval And Fuzzy Uncertainty: Parallel Algorithms, Karen Villaverde, Gang Xiang

Departmental Technical Reports (CS)

Traditional data processing in science and engineering starts with computing the basic statistical characteristics such as the population mean E and population variance V. In computing these characteristics, it is usually assumed that the corresponding data values x1,...,xn are known exactly. In many practical situations, we only know intervals [xi-,xi+] that contain the actual (unknown) values of xi or, more generally, a fuzzy number that describes xi. In this case, different possible values of xi lead, in general, to different values of E and V. In such situations, we are interested in producing the intervals of possible values of E …

How To Reconcile Physical Theories With The Idea Of Free Will: From Analysis Of A Simple Model To Interval And Fuzzy Approaches, Julio C. Urenda, Olga Kosheleva

Departmental Technical Reports (CS)

Most modern physical theories are formulated in terms of differential equations. As a result, if we know exactly the current state of the world, then this state uniquely determines all the future events -- including our own future behavior. This determination seems to contradict the intuitive notion of a free will, according to which we are free to make decisions -- decisions which cannot be determined based on the past locations and velocities of the elementary particles. In quantum physics, the situation is somewhat better in the sense that we cannot determine the exact behavior, but we can still determine …

Towards An Optimal Algorithm For Computing Fixed Points: Dynamical Systems Approach, With Applications To Transportation Engineering, Ruey L. Cheu, Gang Xiang, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical problems, it is desirable to find an equilibrium. For example, equilibria are important in transportation engineering.

Many urban areas suffer from traffic congestion. Intuitively, it may seem that a road expansion (e.g., the opening of a new road) should always improve the traffic conditions. However, in reality, a new road can actually worsen traffic congestion. It is therefore extremely important that before we start a road expansion project, we first predict the effect of this project on traffic congestion.

When a new road is built, some traffic moves to this road to avoid congestion on the other …

How To Measure A Degree Of Mismatch Between Probability Models, P-Boxes, Etc.: A Decision-Theory-Motivated Utility-Based Approach, Luc Longpre, Scott Ferson, W. Troy Tucker

Departmental Technical Reports (CS)

Different models can be used to describe real-life phenomena: deterministic, probabilistic, fuzzy, models in which we have interval-valued or fuzzy-valued probabilities, etc. Models are usually not absolutely accurate. It is therefore important to know how accurate is a given model. In other words, it is important to be able to measure a mismatch between the model and the empirical data. In this paper, we describe an approach of measuring this mismatch which is based on the notion of utility, the central notion of utility theory.

We also show that a similar approach can be used to measure the loss of …

Relations Between Interval Computing And Soft Computing, Vladik Kreinovich

Departmental Technical Reports (CS)

This paper starts with a brief reminder of why data processing and knowledge processing are needed in the first place, why interval and fuzzy methods are needed for data and knowledge processing, and which of the possible data and knowledge processing techniques we should use. Then, we explain how these reasonable soft computing techniques are naturally related with interval computing. Finally, we explain the need for interval-valued fuzzy techniques -- techniques which will be used a lot in our future applications -- and how the transition to such techniques is also related to interval computing.

Towards More Adequate Representation Of Uncertainty: From Intervals To Set Intervals, With The Possible Addition Of Probabilities And Certainty Degrees, J. T. Yao, Y. Y. Yao, Vladik Kreinovich, Paulo Pinheiro Da Silva, Scott A. Starks, Gang Xiang, H. T. Nguyen

Departmental Technical Reports (CS)

In the ideal case of complete knowledge, for each property Pi (such as "high fever", "headache", etc.), we know the exact set Si of all the objects that satisfy this property. In practice, we usually only have partial knowledge. In this case, we only know the set Si- of all the objects about which we know that Pi holds and the set Si+ about which we know that Pi may hold (i.e., equivalently, that we have not yet excluded the possibility of Pi). This pair of sets is called a set interval.

Based on the knowledge of the original properties, …

Extracting Computable Bounds (And Algorithms) From Classical Existence Proofs: Girard Domains Enable Us To Go Beyond Local Compactness, Vladik Kreinovich, Karen Villaverde

Departmental Technical Reports (CS)

In classical mathematics, the existence of a solution is often proven indirectly, non-constructively, without an efficient method for constructing the corresponding object. In many cases, we can extract an algorithm from a classical proof: e.g., when an object is (non-constructively) proven to be unique in a locally compact space (or when there are two such objects with a known lower bound on the distance between them). In many other practical situations, a (seemingly) natural formalization of the corresponding practical problem leads to a non-compact set. In this paper, we show that often, in such situations, we can extract efficient algorithms …

A Library-Based Approach To Translating Ocl Constraints To Jml Assertions For Runtime Checking, Carmen Avila, Guillermo Flores, Jr., Yoonsik Cheon

Departmental Technical Reports (CS)

OCL is a formal notation to specify constraints on UML models that cannot otherwise be expressed by diagrammatic notations such as class diagrams. Using OCL one can document detailed design decisions and choices along with the behavior, e.g., class invariants and method pre and postconditions. However, OCL constraints cannot be directly executed and checked at runtime by an implementation, thus constraint violations may not be detected or noticed, causing many potential development and maintenance problems. In this paper we propose an approach to checking OCL constraints at runtime by translating them to executable JML assertions. The key components of our …

Identification Of Human Gait In Neuro-Rehabilitation: Towards Efficient Algorithms, Naga Suman Kanagala, Martine Ceberio, Thompson Sarkodie-Gyan, Vladik Kreinovich, Roberto Araiza

Departmental Technical Reports (CS)

Many neurological diseases such as stroke, traumatic body injury, spinal cord injury drastically decrease the patient's ability to walk without physical assistance. To re-establish normal gait, patients undergo extensive rehabilitation. At present, rehabilitation requires gait assessment by highly qualified experienced clinicians. To make rehabilitations easier to access and to decrease the rehabilitation cost, it is desirable to automate gait assessment. In precise terms, gait assessment means comparing the recorded patient's gait with a standard (average) gait of healthy people of the same body measurements. One of the problems in this comparison is that patients walk slower; so, to properly compare …

Integrating Random Testing With Constraints For Improved Efficiency And Diversity, Yoonsik Cheon, Antonio Cortes, Martine Ceberio, Gary T. Leavens

Departmental Technical Reports (CS)

Random testing can be fully automated, eliminates subjectiveness in constructing test cases, and increases the diversity of test data. However, randomly generated tests may not satisfy program's assumptions (e.g., method preconditions). While constraint solving can satisfy such assumptions, it does not necessarily generate diverse tests and is hard to apply to large programs. We blend these techniques by extending random testing with constraint solving, improving the efficiency of generating valid test data while preserving diversity. For domains such as objects, we generate input values randomly; however, for values of finite domains such as integers, we represent test data generation as …

Equidecomposability (Scissors Congruence) Of Polyhedra In R^3 And R^4 Is Algorithmically Decidable: Hilbert's 3rd Problem Revisited, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Identifying And Explaining Map Quality Through Provenance: A User Study, Nicholas Ricky Del Rio, Paulo Pinheiro Da Silva

Departmental Technical Reports (CS)

Applications deployed on cyber-infrastructures often rely on multiple data sources and distributed compute resources to access, process, and derive results. When application results are maps, it is possible that non-intentional imperfections can get introduced into the map generation processes because of several reasons including the use of low quality datasets, use of data filtering techniques incompatible for the kind of map to be generated, or even the use of inappropriate mapping parameters, e.g., low-resolution gridding parameters. Without some means for accessing and visualizing the provenance associated with map generation processes, i.e., metadata about information sources and methods used to derive …