Computer Engineering Commons^™

Propitious Checkpoint Intervals To Improve System Performance, Sarala Arunagiri, John T. Daly, Patricia J. Teller

Departmental Technical Reports (CS)

The large scale of current and next-generation massively parallel processing (MPP) systems presents significant challenges related to fault tolerance. For applications that perform periodic checkpointing, the choice of the checkpoint interval, the period between checkpoints, can have a significant impact on the execution time of the application and the number of checkpoint I/O operations performed by the application. These two metrics determine the frequency of checkpoint I/O operations performed by the application, and thereby, the contribution of the checkpoint operations to the I/O bandwidth demand made by the application. In a computing environment where there are concurrent applications competing for …

Experiments In Teaching An Engaging And Demystifying Introduction To Algorithms: Installment 1: Huffman Codes, Alan Siegel, Eric Freudenthal

Departmental Technical Reports (CS)

As is well known -- the Huffman algorithm is a remarkably simple, and is a wonderfully illustrative example of the greedy method in algorithm design. However, the Huffman problem, which is to design an optimal binary character code (or an optimal binary tree with weighted leaves) is intrinsically technical, and its specification is ill-suited for students with modest mathematical sophistication.

This difficulty is circumvented by introducing an alternative 'precursor' problem that is easy to understand, and where this understanding can lead to student-devised solutions: how to merge k sorted lists of varying length together as efficiently as possible. Once students …

Fast Convolution And Fast Fourier Transform Under Interval Uncertainty, Guoqing Liu, Vladik Kreinovich

Departmental Technical Reports (CS)

Convolution y(t), defined as an integral of a(t-s)*x(s) ds, is one of the main techniques in digital signal processing. A straightforward computation of the convolution y(t) requires O(n^2) steps, where n is the number of observations x(t0),...,x(t(n-1)). It is well known that by using the Fast Fourier Transform (FFT) algorithm, we can compute convolution much faster, with computation time O(n*log(n)).

In practice, we only know the signal x(t) and the function a(t) with uncertainty; sometimes, we know them with interval uncertainty, i.e., we know intervals [x-(t),x+(t)] and [a-(t),a+(t)] that contain the actual (unknown) functions x(t) and a(t). In such situations, …

Egyptian Fractions Revisited, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

It is well known that the ancient Egyptians represented each fraction as a sum of unit fractions -- i.e., fractions with unit numerators; this is how they, e.g., divided loaves of bread. What is not clear is why they used this representation. In this paper, we propose a new explanation: crudely speaking, that the main idea behind the Egyptian fractions provides an optimal way of dividing the loaves. We also analyze the related properties of fractions.

A New Justification Of Wang Transform Operator In Financial Risk Analysis, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

One of the most widely used (and most successful) methods for pricing financial and insurance instruments under risk is the Wang transform method. In this paper, we provide a new explanation for the empirical success of Wang's method -- by providing a new simpler justification for the Wang transform.

Asymmetric Heteroskedasticity Models: A New Justification, Songsak Sriboonchitta, Vladik Kreinovich

Departmental Technical Reports (CS)

Most existing econometric models such as ARCH(q) and GARCH(p,q) take into account heteroskedasticity (non-stationarity) of time series. However, the original ARCH(q) and GARCH(p,q) models do not take into account the asymmetry of the market's response to positive and to negative changes. Several heuristic modifications of ARCH(q) and GARCH(p,q) models have been proposed that take this asymmetry into account. These modifications turned out to be very adequate and efficient in describing the econometric time series. In this paper, we propose a justification of these heuristic modifications -- and thus, an explanation of their empirical efficiency.

Quantum Computing As A Particular Case Of Computing With Tensors, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

One of the main potential applications of uncertainty in computations is quantum computing. In this paper, we show that the success of quantum computing can be explained by the fact that quantum states are, in effect, tensors.

A Possible Way To Avoid Heat Death, Nitaya Buntao, Narunchara Katemee, Vladik Kreinovich

Departmental Technical Reports (CS)

A disturbing consequence of the traditional thermodynamics is the possibility of heat death, when the Universe arrives at the state with the largest possible value of the entropy and all the processes will stop. In this paper, we show that one possible way to avoid this consequence is to consider situations in which the entropy never attains its maximum -- and thus, the heat death state is not possible. We show that such situations can have physical sense -- e.g., they naturally appear in boostrap models.

Towards Neural-Based Understanding Of The Cauchy Deviate Method For Processing Interval And Fuzzy Uncertainty, Vladik Kreinovich, Hung T. Nguyen

Departmental Technical Reports (CS)

One of the most efficient techniques for processing interval and fuzzy data is a Monte-Carlo type technique of Cauchy deviates that uses Cauchy distributions. This technique is mathematically valid, but somewhat counterintuitive. In this paper, following the ideas of Paul Werbos, we provide a natural neural network explanation for this technique.

Estimating Risk Under Interval Uncertainty: Sequential And Parallel Algorithms, Vladik Kreinovich, Hung T. Nguyen, Songsak Sriboonchitta

Departmental Technical Reports (CS)

In traditional econometrics, the quality of an individual investment -- and of the investment portfolio -- is characterized by its expected return and its risk (variance). For an individual investment or portfolio, we can estimate the future expected return and a future risk by tracing the returns x₁, ..., x_n of this investment (and/or similar investments) over the past years, and computing the statistical characteristics based on these returns. The return (per unit investment) is defined as the selling of the corresponding financial instrument at the ends of, e.g., a one-year period, divided by the buying price …

Mathematical Justification Of Spectral/Covariance Techniques: On The Example Of Arc Detection, Jan Beck, David Nemir, Vladik Kreinovich

Departmental Technical Reports (CS)

Detecting arcing faults is an important but difficult-to-solve practical problem. Many existing methods of arc detection are based upon acquiring a signal that is proportional to current and then making an analysis of the signal's power spectrum (or, equivalently, its covariance function). Since the power spectrum, i.e., the absolute values of the Fourier transform, carries only partial information about the signal, a natural question is: why should we restrict ourselves to the use of this partial information? A related question is caused by the fact that even the most efficient methods still miss some arcing faults and/or lead to false …

Computing With Tensors: Potential Applications Of Physics-Motivated Mathematics To Computer Science, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we explain what are tensors and how tensors can help in computing.

Intelligence Techniques Are Needed To Further Enhance The Advantage Of Groups With Diversity In Problem Solving, Oscar Castillo, Patricia Melin, J. Esteban Gamez, Vladik Kreinovich, Olga Kosheleva

Departmental Technical Reports (CS)

In practice, there are many examples when the diversity in a group enhances the group's ability to solve problems -- and thus, leads to more efficient groups, firms, schools, etc. Several papers, starting with the pioneering research by Scott E. Page from the University of Michigan at Ann Arbor, provide a theoretical justification for this known empirical phenomenon. However, when the general advise of increasing diversity is transformed into simple-to-follow algorithmic rules (like quotas), the result is not always successful. In this paper, we prove that the problem of designing the most efficient group is computationally difficult (NP-hard). Thus, in …

An Aspect-Based Approach To Checking Design Constraints At Run-Time, Yoonsik Cheon, Carmen Avila, Steve Roach, Cuauhtemoc Munoz, Neith Estrada, Valeria Fierro, Jessica Romo

Departmental Technical Reports (CS)

Design decisions and constraints of a software system can be specified precisely using a formal notation such as the Object Constraint Language (OCL). However, they are not executable, and assuring the conformance of an implementation to its design is hard. The inability of expressing design constraints in an implementation and checking them at runtime invites, among others, the problem of design drift and corrosion. We propose runtime checks as a solution to mitigate this problem. The key idea of our approach is to translate design constraints written in a formal notation such as OCL into aspects that, when applied to …

On Chromatic Numbers Of Space-Times: Open Problems, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

A Paradox Of Altruism: How Caring About Future Generations Can Result In Poverty For Everyone (Game-Theoretic Analysis), Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

Political and social activists are rightfully concerned about future generations: whenever a country borrows money, or an environmental situation worsens, this means, in effect, that we impose an additional burdens on future generations. There is clearly a conflict between the present generation's actions and interests and the welfare of the future generations. There exists a mathematical toolbox that provides solutions to many well-defined conflict situations: namely, the toolbox of game theory. It therefore seems reasonable to apply game theory techniques to the conflict between the generations. In this paper, we show that we need to be very cautious about this …

Viability Of Travel-Time Sensitivity Testing For Estimating Uncertainty Of Tomographic Velocity Models: A Case Study, Matthew G. Averill, Kate C. Miller, Vladik Kreinovich, Aaron A. Velasco

Departmental Technical Reports (CS)

Seismic tomography is now a common approach to estimating velocity structure of the Earth, regardless of whether the data sources are earthquake recordings or controlled sources such as explosions, airguns or Vibroseis. Seismic tomography is convenient to implement because it requires little to no a priori knowledge of Earth structure and is much less time consuming than forward modeling schemes. Despite its convenience, the method still lacks satisfactory quantitative assessments of model reliability. Here we explore the viability of applying travel-time sensitivity testing that uses a modified Cauchy distribution as its statistical foundation to assessing the uncertainty in velocity models …

A New Simplified Derivation Of Nash Bargaining Solution, Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

In the 1950s, the Nobel Prize winner John F. Nash has shown that under certain conditions, the best solution to the bargaining problem is when the product of the (increase in) utilities is the largest. Nash's derivation assumed that we are looking for strategies that assign a single situation to each bargaining situation. In this paper, we propose a simplified derivation of Nash bargaining solution that does not requires this assumption.

Asymmetric Information Measures: How To Extract Knowledge From An Expert So That The Expert's Effort Is Minimal, Hung T. Nguyen, Vladik Kreinovich, Elizabeth N. Kamoroff

Departmental Technical Reports (CS)

Knowledge acquisition is when we ask experts questions, and put the answers into the computer system. Since this is a very time-consuming task, it is desirable to minimize the effort of an expert.

As a crude estimate for this effort, we can take a number of binary (yes-no) questions that we ask. The procedure that minimizes this number is binary search.

This approach does not take into account that people often feel more comfortable answering "yes" than answering "no". So, to make our estimates more realistic, we will take into consideration that for a negative answer the effort is bigger. …

Current Financial Crisis And Inadequate Uncertainty Processing: A Comment, Tanja Magoc, Vladik Kreinovich

Departmental Technical Reports (CS)

No abstract provided.

Computational Methods For Investment Portfolio: The Use Of Fuzzy Measures And Constraint Programming For Risk Management, Tanja Magoc, Francois Modave, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

Computational intelligence techniques are very useful tools for solving problems that involve understanding, modeling, and analysis of large data sets. One of the numerous fields where computational intelligence has found an extremely important role is finance. More precisely, optimization issues of one's financial investments, to guarantee a given return, at a minimal risk, have been solved using intelligent techniques such as genetic algorithm, rule-based expert system, neural network, and support-vector machine. Even though these methods provide good and usually fast approximation of the best investment strategy, they suffer some common drawbacks including the neglect of the dependence among among criteria …

Trustmap: Towards Trust Recommendations For Maps, Paulo Pinheiro Da Silva, Nicholas Ricky Del Rio, Vladik Kreinovich, Alejandro Castaneda

Departmental Technical Reports (CS)

The web is a rich environment for exchanging spatial information. When spatial information is shared in the form of images, i.e., maps, these images almost never come with meta-information about how they were generated. This kind of meta-information is often called knowledge provenance. Access to knowledge provenance may facilitate users to make informed decisions about the quality of maps. In this paper, we propose TrustMap, a new approach for enhancing maps with trust recommendations. For a given map, TrustMap can generate recommendations from the knowledge provenance and a network of trust relations between sources of information used to derive the …

Maximum Entropy In Support Of Semantically Annotated Datasets, Paulo Pinheiro Da Silva, Vladik Kreinovich, Christian Servin

Departmental Technical Reports (CS)

One of the important problems of semantic web is checking whether two datasets describe the same quantity. The existing solution to this problem is to use these datasets' ontologies to deduce that these datasets indeed represent the same quantity. However, even when ontologies seem to confirm the identify of the two corresponding quantities, it is still possible that in reality, we deal with somewhat different quantities. A natural way to check the identity is to compare the numerical values of the measurement results: if they are close (within measurement errors), then most probably we deal with the same quantity, else …

Additional Information About American And Arab Perceptions Of An Arabic Turn-Taking Cue, Nigel Ward, Yaffa Al Bayyari

Departmental Technical Reports (CS)

This technical report is a supplement to "American and Arab perceptions of an Arabic turn-taking cue", a paper submitted to the Journal of Cross-Cultural Psychology. It provides additional details, discussion, figures, tables, and references relating to the main finding, that English speakers tend to misinterpret the prosodic pattern used in Arabic to cue back-channel responses, perceiving it as an expression of negative affect. It also describes an experimental demonstration that being able to detect and respond to this prosodic pattern in dialog can increase native-speaker perceptions of the social effectiveness of learners.

Verified Methods For Computing Pareto Sets: General Algorithmic Analysis, Boglarka G.-Toth, Vladik Kreinovich

Departmental Technical Reports (CS)

In many engineering problems, we face multi-objective optimization, with several objective functions f1,...,fn. We want to provide the user with the Pareto set -- set of all possible solutions x which cannot be improved in all categories (i.e., for which fj(x')>=f_j(x) for all j and fj(x')>fj(x) for some j is impossible). The user should be able to select an appropriate trade-off between, say, cost and durability. We extend the general results about the (verified) algorithmic computability of maxima locations to show that Pareto sets can also computed.

Towards A More Adequate Use Of Interval-Valued Fuzzy Techniques In Intelligent Control: A Fuzzy Analogue Of Unimodality, Van Nam Huynh, Vladik Kreinovich

Departmental Technical Reports (CS)

It is known that interval-valued fuzzy sets provide a more adequate description of expert uncertainty than the more traditional "type-1" (number-valued) fuzzy techniques. In the current approaches for using interval-valued fuzzy techniques, it is usually assumed that all fuzzy sets m(x) from the interval [l(x),u(x)] are possible. In this paper, we show that it is reasonable to restrict ourselves only to fuzzy numbers m(x), i.e., "unimodal" fuzzy sets. We also describe feasible algorithms for implementing thus modified intelligent control.

Towards A Combination Of Interval And Ellipsoid Uncertainty, Vladik Kreinovich, Arnold Neumaier, Gang Xiang

Departmental Technical Reports (CS)

In many real-life situations, we do not know the probability distribution of measurement errors but only upper bounds on these errors. In such situations, once we know the measurement results, we can only conclude that the actual (unknown) values of a quantity belongs to some interval. Based on this interval uncertainty, we want to find the range of possible values of a desired function of the uncertain quantities. In general, computing this range is an NP-hard problem, but in a linear approximation, valid for small uncertainties, there is a linear time algorithm for computing the range. In other situations, we …

Hypothesis Testing With Interval Data: Case Of Regulatory Constraints, Sa-Aat Niwitpong, Hung T. Nguyen, Ingo Neumann, Vladik Kreinovich

Departmental Technical Reports (CS)

In many practical situations, there exist regulatory thresholds: e.g., a concentration of certain chemicals in the car exhaust cannot exceed a certain level, etc. If we know the exact value of the corresponding quantity, then we can immediately tell whether, e.g., a car design resulting in this value is acceptable (below the threshold) or not acceptable (above the threshold). In practice, however, the value of the desired quantity comes from measurements or from expert estimates; in both cases, the resulting estimates are not 100% accurate. It is therefore necessary to make an accept/reject decision based on this estimate, i.e., based …

Computing Degrees Of Subsethood And Similarity For Interval-Valued Fuzzy Sets: Fast Algorithms, Hung T. Nguyen, Vladik Kreinovich

Departmental Technical Reports (CS)

We propose fast algorithms for computing degrees of subsethood and similarity for interval-valued fuzzy sets.

Choquet Integrals And Owa Criteria As A Natural (And Optimal) Next Step After Linear Aggregation: A New General Justification, Francois Modave, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In multi-criteria decision making, it is necessary to aggregate (combine) utility values corresponding to several criteria (parameters). The simplest way to combine these values is to use linear aggregation. In many practical situations, however, linear aggregation does not fully adequately describe the actual decision making process, so non-linear aggregation is needed.

From the purely mathematical viewpoint, the next natural step after linear functions is the use of quadratic functions. However, in decision making, a different type of non-linearities are usually more adequate than quadratic ones: non-linearities like OWA or Choquet integral that use min and max in addition to linear …