Technical reports


List of technical reports of year 2010

Vandebril, Raf and Del Corso, Gianna M.
A unification of unitary similarity transforms to compressed representations
December 5, 2014
UnipiEprints view

In this paper a new framework for transforming arbitrary matrices to compressed representations is presented. The framework provides a generic way of transforming a matrix via unitary similarity transformations to e.g.\ Hessenberg, Hessenberg\-/like and combinations of both. The new algorithms are deduced, based on the $QR$-factorization of the original matrix. Based on manipulations with Givens transformations, all the algorithms consists of eliminating the correct set of Givens transformations, resulting in a matrix obeying the desired structural constraints. Based on this new reduction procedure we investigate further correspondences such as irreducibility, unicity of the reduction procedure and the link with (rational) Krylov methods. The unitary similarity transform to Hessenberg\-/like form as presented here, differs<br />significantly from the one presented in earlier work. Not only does it use less Givens transformations to obtain the desired structure, also the convergence to rational Ritz values is not observed in the standard way.

Bevilacqua, Roberto and Bozzo, Enrico and Del Corso, Gianna M.
Qd-type methods for quasiseparable matrices
December 4, 2014
UnipiEprints view

In the last few years many numerical techniques for computing eigenvalues of structured rank matrices have been proposed. Most of them are<br />based on $QR$ iterations since, in the symmetric case, the rank structure is preserved and high accuracy is guaranteed. In the unsymmetric<br />case, however, the $QR$ algorithm destroys the rank structure, which is instead preserved if $LR$ iterations are used. We consider a wide<br />class of quasiseparable matrices which can be represented in terms of the same parameters involved in their Neville factorization. This<br />class, if assumptions are made to prevent possible breakdowns, is closed under $LR$ steps. Moreover, we propose an implicit shifted $LR$<br />method with a linear cost per step, which resembles the qd method for tridiagonal matrices. We show that for totally nonnegative<br />quasiseparable matrices the algorithm is stable and breakdowns cannot occur, if the Laguerre shift, or other shift strategy preserving<br />nonnegativity, is used. Computational evidence shows that good accuracy is obtained also when applied to symmetric positive definite<br />matrices.<br />

Aldinucci, Marco and Danelutto, Marco and Kilpatrick, Peter and Xhagjika, Vamis
LIBERO: a LIghtweight BEhaviouRal skeletOn framework
December 4, 2014
UnipiEprints view

We describe a lightweight prototype framework designed for experimentation with behavioural skeletons. A behavioural skeleton is a component implementing a well-known parallelism exploitation pattern and a rule-based autonomic manager taking care of some non-functional feature related to the parallel computation. Our prototype supports multiple autonomic managers within the same behavioural skeleton, each taking care of a different functional concern. The different managers in the behavioural skeleton coordinate themselves in such a way that a global, user-provided SLA can be satisfied. We discuss experiments that validate the manager coordination protocol, and the overall prototype functionality. The prototype is built on top of plain Java and employs JBoss rules for management. We present experimental results that demonstrate the operation of our prototype and allow overheads to be evaluated.

Bacciu, Davide and Micheli, Alessio and Sperduti, Alessandro
A Bottom-up Hidden Tree Markov Model
December 4, 2014
UnipiEprints view

Hidden Tree Markov Models describe probability distributions over tree-structured data by defining a top-down generative process from the root to the leaves of the tree. We provide a novel compositional hidden tree Markov model that inverts the generative process, allowing hidden states to better correlate and model the co-occurrence of substructures among the child subtrees of internal nodes. To this end, we introduce a mixed memory approximation that factorizes the joint children-to-parent state transition matrix as a mixture of pairwise transitions. This Technical Report provides and in-depth introduction to the Bottom-Up Hidden Tree Markov Model, including the details of the learning and inference procedures.

Cioni, Lorenzo
Introduzione alla System Dynamics
December 4, 2014
UnipiEprints view

This Technical Report, written in Italian, represents a short introduction to some basic concepts of System Dynamics. The focus is mainly on Causal Loop diagrams and on Flow diagrams and many examples are given of construction of such diagrams. It also contains a discussion of how differential equation of order higher than the first order can be represented and numerically solved by using Vensim models.<br />Reports of errors and inaccuracies of any kind are appreciated and really welcome.<br />

Aldinucci, Marco and Danelutto, Marco and Kilpatrick, Peter and Meneghin, Massimiliano and Torquati, Massimo
Accelerating sequential programs using FastFlow and self-offloading
December 4, 2014
UnipiEprints view

<p class="MsoPlainText" style="MARGIN: 0cm 0cm 0pt"><font size="3"><font face="Calibri">FastFlow is a programming environment specifically targeting cache-coherent shared-memory multi-cores. FastFlow is implemented as a stack of C++ template libraries built on top of lock-free (fence-free) synchronization mechanisms. In this paper we present a further evolution of FastFlow enabling programmers to offload part of their workload on a dynamically created software accelerator running on unused CPUs. The offloaded function can be easily derived from pre-existing sequential code. We emphasize in particular the effective trade-off between human productivity and execution efficiency of the approach.</font></font></p>

Recchia, Raffaella and Scutellà, Maria Grazia
Experiments with robust asset allocation strategies: classical versus relaxed robustness
December 4, 2014
UnipiEprints view

Aim of this paper is to compare alternative forms of robustness in the context of portfolio asset allocation. Starting with the concept of convex risk measures, a new family of models, called models, is firstly proposed where not only the values of the uncertainty parameters, but also their degree of feasibility are specified. This relaxed form of robustness is obtained by exploiting the link between convex risk measures and classical robustness. Then, we test some norm-portfolio models, as well as various robust strategies from the literature, with real market data on three different data sets. The objective of the computational study is to compare alternative forms of relaxed robustness - the relaxed robustness characterizing the norm portfolio models, the so-called soft robustness and the CVaR robustness. In addition, the models above are compared to a more classical robust model from the literature, in order to experiment similarities and dissimilarities between robust models based on convex risk measures and more traditional robust approaches. To the best of our knowledge, this is the first attempt at comparing robust strategies of different kinds in the framework of portfolio asset allocation.

Scutellà, Maria Grazia
Hardness of some optimal oblivious routing generalizations
December 4, 2014
UnipiEprints view

A generalization of the robust network design problem with oblivious routing is investigated in (Scutella', 2009), where the (uncertain) demands are served through two alternative routing templates. As indicated in that paper, it is an open issue as to whether the proposed problem, called (2-RND), is polynomially solvable or is NP-Hard. In this note we solve the issue by proving that (2-RND), as well as some generalizations, are NP-Hard. The hardness result holds true also when some routing templates are given as input data. This strengthens the results in (Scutella', 2009), where special (2-RND) cases are devised which are tractable from a computational perspective.

Vandebril, Raf and Del Corso, Gianna M.
An implicit multishift $QR$-algorithm for Hermitian plus low rank matrices
December 4, 2014
UnipiEprints view

Download (html PUBLIC "-//W3) abstract

Hermitian plus possibly non-Hermitian low rank matrices can be efficiently reduced into Hessenberg form. The resulting Hessenberg matrix can still be written as the sum of a Hermitian plus low rank matrix. <br /><br />In this paper we develop a new implicit multishift $QR$-algorithm for Hessenberg matrices, which are the sum of a Hermitian plus a possibly non-Hermitian low rank correction.<br /><br />The proposed algorithm exploits both the symmetry and low rank structure to obtain a $QR$-step involving only $\mO{n}$ floating point operations instead of the standard $\mO{n^2}$ operations needed for performing a $QR$-step on a Hessenberg matrix. The algorithm is based on a suitable<br />$\mO{n}$ representation of the Hessenberg matrix. The low rank parts present in both the Hermitian and low rank part of the sum are compactly stored by a sequence of Givens transformations and few vectors.<br /><br />Due to the new representation, we cannot apply classical deflation techniques for Hessenberg matrices. A new, efficient technique is developed to overcome this problem.<br /><br />Some numerical experiments based on matrices arising in applications are performed.<br />The experiments illustrate effectiveness and accuracy of both the $QR$-algorithm and the newly developed deflation technique. <br />

Luccio, Fabrizio and Mesa Enriquez, Antonio and Pagli, Linda
Lower Bounds on the Rotation Distance of Binary Trees
December 4, 2014
UnipiEprints view

The rotation distance d(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T) <= 2n-6, a well known conjecture states that there are trees for which this bound is sharp for any value of n >= 11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some ``regular'' tree structures for which d(S,T) = 3n/2-O(1), or d(S,T) = 5n/3-O(1).

Dell'Acqua, Pietro and Frangioni, Antonio and Serra Capizzano, Stefano
Multi-iterative techniques of Multigrid type for solving large linear systems with structure of graph
December 4, 2014
UnipiEprints view

We consider multi-iterative techniques of multigrid type for the numerical solution of large linear systems with (weighted) structure of graph. We combine proper coarser-grid operators with auxiliary techniques. We show that the most effective smoothers have to be of Krylov type with spanning tree preconditioners, while the projectors have to be designed for maintaining as much as possible the structure of graph matrix at the inner levels. Some necessary and sufficient conditions are proved; in this framework it is possible to explain why the classical projectors inherited from differential equations are good in the differential context and why they behave unsatisfactorily for unstructured graphs. Several numerical experiments have been conducted showing that our approach is effective even in very difficult cases where the known approaches are rather slow.

Aldinucci, Marco and Ruggieri, Salvatore and Torquati, Massimo
Porting Decision Tree Algorithms to Multicore using FastFlow
December 4, 2014
UnipiEprints view

The whole computer hardware industry embraced multicores. For these machines, the extreme optimisation of sequential algorithms is no longer sufficient to squeeze the real machine power, which can be only exploited via thread-level parallelism. Decision tree algorithms exhibit natural concurrency that makes them suitable to be parallelised. This paper presents an approach for easy-yet-efficient porting of an implementation of the C4.5 algorithm on multicores. The parallel porting requires minimal changes to the original sequential code, and it is able to exploit up to 7X speedup on an Intel dual-quad core machine.

Bodei, Chiara and Dung, Dinh and Gian Luigi, Ferrari
Safer in the Clouds
December 4, 2014
UnipiEprints view

We outline the design of a framework for modelling <br />cloud computing systems.<br />The approach is based on a declarative programming model which takes the form of a lambda-calculus enriched with suitable mechanisms to express and enforce application-level security policies governing usages of resources available in the clouds. <br />We will focus on the server side of cloud systems, by adopting a pro-active approach, where explicit security policies regulate server's behaviour. <br />

Cioni, Lorenzo
A few notes on the Borda and Condorcet methods
December 4, 2014
UnipiEprints view

The present Technical Report contains a short analysis of both the Borda and the Condorcet methods. We start with a description of both methods in their twofold roles: of methods for defining a winning alternative from a set of available alternatives,} of possible outranking methods over a set of alternatives. We then discuss the properties of each method and analyze them with regard to the conditions posed by the Arrow's impossibility theorem. The last step, that represents the core part of the Technical Report, is represented by the search of possible relations between the two methods. The Technical Report closes with the proposal of a composed outranking method based on both the Borda and the Condorcet methods executed on the same profiles of preferences. As usual, reports of errors and inaccuracies are gratefully appreciated.

Cioni, Lorenzo
An inverse or negative auction
December 4, 2014
UnipiEprints view

In this Technical Report we describe a type of auction mechanism where the auctioneer <strong>A</strong> wants to auction an item among a certain number of bidders of a set <strong>B</strong> that submit bids in the auction with the aim of not getting that item. Owing to this feature we call this mechanism an <strong>inverse</strong> or <strong>negative</strong> auction. The main motivation of this mechanism is that both the bidders and the auctioneer give a negative value to the auctioned item (and so they see it as a bad rather than a good). The mechanism is presented in its basic simple version and with some possible extensions that account for the payment of a fee for not attending the auction, the interactions among the bidders and the presence of other supporting actors.

Aldinucci, Marco and Bracciali, Andrea and Liò, Pietro and Sorathiya, Anil and Torquati, Massimo
StochKit-FF: Efficient Systems Biology on Multicore Architectures
December 4, 2014
UnipiEprints view

The stochastic modelling of biological systems is an informative, and in some cases, very adequate technique, which may however result in being more expensive than other modelling approaches, such as differential equations. We present StochKit-FF, a parallel version of StochKit, a reference toolkit for stochastic simulations. StochKit-FF is based on the FastFlow programming toolkit for multicores and exploits the novel concept of selective memory. We experiment StochKit-FF on a model of HIV infection dynamics, with the aim of extracting information from efficiently run experiments, here in terms of average and variance and, on a longer term, of more structured data.

Cisternino, Antonio and Ferragina, Paolo and Morelli, Davide and Coppola, Massimo
Information processing at work: On a theory for experimental algorithm complexity
December 4, 2014
UnipiEprints view

<p>It is common experience to upgrade firmware of mobile devices and obtain longer battery life, living proof of how software affects power consumption of a device. Despite this empirical observation, there is a lack for models and methodologies correlating computations with power consumption [3-5]. In this paper we propose an experimental approach to computational complexity and a methodology for conducting measures which result independent of the underlying system running the algorithm/software to be tested. Early experimental results are presented and discussed, showing that our methodology is robust and can be used in many settings. We also introduce the foundations of a theory for experimental algorithm complexity, which mimics what is predicted by the classic theory of computational complexity (big-O or Theta notations), except for some notable exceptions that we highlight and comment. This theory is validated in many scenarios, by considering several architectures and algorithms. Because of the relation between time complexity and energy consumption, we may suggest that our work measures the “information work”: namely, the energy required for performing information processing.</p><p />

Bernasconi, Anna and Ciriani, Valentina and Luccio, Fabrizio and Pagli, Linda
Compact DSOP Forms Derived from SOP Expressions
December 4, 2014
UnipiEprints view

We give a new heuristic for Disjoint Sum-of-Products (DSOP) minimization of a Boolean function $f$, based on a new criterion for product selection. Starting from a Sum-of-Products (SOP) $S$ of $f$, i.e., a set of cubes covering the minterms of $f$, we assign a weight $w(p)$ to each product (cube) $p$ in $S$, where $w(p)$ depends on the intersection of $p$ with the other cubes of $S$. We assign higher weights to the cubes that, if selected in a DSOP, would generate a higher fragmentation of the other cubes. Disjoint cubes are then selected for increasing value of $w$ and decreasing size, recomputing the SOP on the residual function at different possible stages as a trade-off between quality of result and computational time. We also propose a heuristic for computing partial DSOP forms, i.e., SOP forms whose cubes cover exactly once a given subset of minterms of the function, and more than once the remaining minterms.A set of experiments conducted on major benchmark functions show that our method, with all its variants, always generates better results than the ones of previous heuristics, including the one based on a BDD representation of $f$. These experiments have also outlined how re-synthesizing the residual function in SOP form seems to be crucial for obtaining compact DSOPs.

Bigi, Giancarlo and Adela, Capata and Gabor, Kassay
Existence results for strong vector equilibrium problems and their applications
December 4, 2014
UnipiEprints view

New existence results for the strong vector equilibrium problem are presented, relying on a well-known separation theorem in infinite dimensional spaces. The main results are applied to strong cone saddle-points and strong vector variational inequalities providing new existence results, and furthermore they allow to recover an earlier result from the literature. <br />

Cioni, Lorenzo
A purely probabilistic candle auction
December 4, 2014
UnipiEprints view

<p>Candle auctions have been used in the past as a variant of the English auction with a random termination time associated either to the going out of a candle or to the falling of a needle inserted in a random position in a burning candle.<br />In this case such auctions are used by the auctioneer A for the allocation of a <strong>good</strong> to one of the n bidders b<sub>i</sub> of the set B.<br />Our basic motivation for the use of this type of auctions is the following.<br />We are planning to use such auctions for the allocation of a <strong>chore</strong> at one b<sub>i</sub> from the set B whose members have been selected by A using a set of private criteria that do not depend on the willingness to attend of the single bidders.<br />The to be selected bidder has to be chosen from the set B given that the available information about these bidders are imprecise or fuzzy. These features prevent the profitable and direct selection of a suitable bidder with the guarantee of choosing the best one.<br />For this reason we plan to adopt an auction mechanism where the bidders pay for not getting the chore but one of them has to get it though he also receives a compensation for being the <strong>wining bidder</strong>.<br />The compensation to the winning bidder derives him form the other bidders, the so called <strong>losing bidders</strong>, and is accumulated during the various steps or rounds on which the auction is based.</p><p />

Torquati, Massimo
Single-Producer/Single-Consumer Queues on Shared Cache Multi-Core Systems
December 4, 2014
UnipiEprints view

Using efficient point-to-point communication channels is critical for implementing fine grained parallel program on modern shared cache multi-core architectures.<br />This report discusses in detail several implementations of wait-free Single-Producer/Single-Consumer queue (SPSC), and presents a novel and efficient algorithm for the implementation of an unbounded wait-free SPSC queue (uSPSC). The correctness proof of the new algorithm, and several performance measurements based on simple synthetic benchmark and microbenchmark, are also discussed.



NOTE. Starting January 2015 Technical reports can be inserted in the Open Access repository UnipiEprints.
Once published, they will be visible also in these pages. The old TR service is no longer maintained.

Data imported from UnipiEprints