Kiekvienas mobilus įrenginys turi bateriją, o tai reiškia, kad jų darbo laikas ribotas, kadangi nėra išrasta ilgaamžė baterija. Todėl šiuo metu egzistuojanti problema - kaip pasiekti, kuo ilgesnį mobiliojo įrenginio darbo laiką, be papildomo pakrovimo. Darbo metu naudojamas mobilus įrenginys - delninukas. Iš visų delninuko baterijos energiją suvartojančių komponentų visas dėmesys skiriamas procesoriui ir atminčiai. Tyrimo metu buvo apkrautas procesorius ir atmintis ir stebimi atitinkami baterijos parametrai. Apkrovimui naudojama paprastų ir išretintų matricų saugomų stulpelių metodu daugyba. Išretintų matricų daugybos metu užimama mažiau atminties, o procesorius atlieka daugiau komandų lyginant su paprastu metodu, kuris užima daugiau atminties. Iš gautų rezultatų pamatėme, kad išretintų matricų saugomų stulpelių metodu daugyba yra daug efektyvesnė negu paprastų matricų daugyba. Todėl kuriant programas, kur reikia naudoti matricas geriau naudoti išretintų matricų stulpelių saugojimo metodo daugybą, kadangi galima sutrumpinti operacijos vykdymo laika, sunaudoti mažiau baterijos resursų ir sutaupyti atminties. / Nowadays major problem is energy consumtion in portable devices which has a battery. In this job we have evaluated energy consumption for Pocket PC. We wanted to see memory and processor influence in battery energy consumption. We have created a program which can do matrix multiplication and sparse matrix „storage by columns“ multiplication. During multiplication program takes battery information and saves it into the file. After that I have investigated the result and saw, that sparse matrix storage by columns multiplication is much more effectived than normal matrix multiplication. Sparce matrix storage by columns multiplication take less memory and more processor commands then normal matrix multiplication. We suggest to use sparse matrix storage by columns model instead simple model, because you can save much more operation time, battery resources and memory.

This thesis presents the mathematical analysis of a continuous-times system for sparse signal recovery. Sparse recovery arises in Compressed Sensing (CS), where signals of large dimension must be recovered from a small number of linear measurements, and can be accomplished by solving a complex optimization program. While many solvers have been proposed and analyzed to solve such programs in digital, their high complexity currently prevents their use in real-time applications. On the contrary, a continuous-time neural network implemented in analog VLSI could lead to significant gains in both time and power consumption. The contributions of this thesis are threefold. First, convergence results for neural networks that solve a large class of nonsmooth optimization programs are presented. These results extend previous analysis by allowing the interconnection matrix to be singular and the activation function to have many constant regions and grow unbounded. The exponential convergence rate of the networks is demonstrated and an analytic expression for the convergence speed is given. Second, these results are specialized to the L1-minimization problem, which is the most famous approach to solving the sparse recovery problem. The analysis relies on standard techniques in CS and proves that the network takes an efficient path toward the solution for parameters that match results obtained for digital solvers. Third, the convergence rate and accuracy of both the continuous-time system and its discrete-time equivalent are derived in the case where the underlying sparse signal is time-varying and the measurements are streaming. Such a study is of great interest for practical applications that need to operate in real-time, when the data are streaming at high rates or the computational resources are limited. As a conclusion, while existing analysis was concentrated on discrete-time algorithms for the recovery of static signals, this thesis provides convergence rate and accuracy results for the recovery of static signals using a continuous-time solver, and for the recovery of time-varying signals with both a discrete-time and a continuous-time solver.

In this thesis, we are concerned with content dissemination in mobile ad hoc networks. The scope of content dissemination is limited by network capacity, and sometimes the price to be paid for securing faster delivery. In the first part of the thesis, we address the issue of finding the maximum throughput that a mobile ad-hoc network can support. We have assumed that there is no price involved, and all nodes work as a team. The problem of determining the capacity region has long been known to be NP-hard even for stationary nodes. Mobility introduces an additional dimension of complexity because nodes now also have to decide when they should initiate route discovery. Since route discovery involves communication and computation overhead, it should not be invoked very often. On the other hand, mobility implies that routes are bound to become stale, resulting in sub-optimal performance if routes are not updated. We attempt to gain some understanding of these effects by considering a simple one-dimensional network model. The simplicity of our model allows us to use stochastic dynamic programming (SDP) to find the maximum possible network throughput with ideal routing and medium access control (MAC) scheduling. Using the optimal value as a benchmark, we also propose and evaluate the performance of a simple threshold-based heuristic. Unlike the optimal policy which requires considerable state information, the proposed heuristic is simple to implement and is not overly sensitive to the threshold value. We find empirical conditions for our heuristic to be near-optimal. Also, network scenarios when our heuristic does not perform very well are analyzed. We provide extensive numerical analysis and simulation results for different parameter settings of our model. Interestingly, we observe that in low density network the average throughput can first decrease with mobility, and then increase. This motivates us to study a mobile ad-hoc network when it is sparse and in a generalized environment, such as when movement of nodes is in a two-dimension plane. Due to sparseness, there are frequent disruptions in the connections and there may not be any end-to-end connection for delivery. The mobility of nodes may be used for carrying the forwarded message to the destination. This network is also known as a delay tolerant network. In the rest part of the thesis, we consider the relay nodes to be members of a group that charges a price for assisting in message transportation. First, we solve the problem of how to select first relay node when only one relay node can be chosen from a given number of groups. Next, we solve two problems, namely price-constrained delay minimization, and delay-constrained price optimization.

Neste trabalho foi realizado um grande levantamento de técnicas de esparsidade relacionadas a sistemas estáticos de energia elétrica. Tais técnicas visam, do ponto de vista computacional, ao aumento da eficiência na solução de rede elétrica objetivando, além da resolução em si, a redução dos requisitos de memória, armazenamento e tempo de processamento. Para tanto, uma extensa revisão bibliográfica foi compilada, apresentando um posicionamento histórico e uma ampla visão do desenvolvimento teórico. Os testes comparativos realizados para sistemas de 14, 30, 57 e 118 barras, sobre a implantação de três das técnicas mais empregadas, apontou a Bi-fatoração como tendo o melhor desempenho médio. Para sistemas pequenos, a Eliminação Esparsa e Sintética de Gauss apresentou melhores resultados. Este trabalho fornecerá subsídios conceituais e metodológicos a técnicos e pesquisadores da área. / In this work a great survey of sparsity techniques related to static systems of electric power was accomplished. Such techniques seek, for of the computational point of view, the increase of the efficiency in the solution of the electric net aiming, besides the resolution of itself, the reduction of memory requirements, the storage and time processing. For that, an extensive bibliographic review was compiled providing a historic positioning and a broad view of theoretic development. The comparative tests accomplished for systems of 14,30, 57 and 118 buses, on the implementation of three of the most employed techniques, it pointed out an bi-factorisation as best medium performance. For small systems, the sparse symmetric Gaussian elimination showed the best results. This work will supply conceptual and methodological subsidies to technicians and researchers of the area.

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures. / New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures.

The brain is a complex organ that is computationally strong. Recent research in the field of neurobiology help scientists to better understand the working of the brain, especially how the brain represents or codes external signals. The research shows that the neural code is sparse. A sparse code is a code in which few neurons participate in the representation of a signal. Neurons communicate with each other by sending pulses or spikes at certain times. The spikes send between several neurons over time is called a spike train. A spike train contains all the important information about the signal that it codes. This thesis shows how sparse coding can be used to do speech recognition. The recognition process consists of three parts. First the speech signal is transformed into a spectrogram. Thereafter a sparse code to represent the spectrogram is found. The spectrogram serves as the input to a linear generative model. The output of themodel is a sparse code that can be interpreted as a spike train. Lastly a spike train model recognises the words that are encoded in the spike train. The algorithms that search for sparse codes to represent signals require many computations. We therefore propose an algorithm that is more efficient than current algorithms. The algorithm makes it possible to find sparse codes in reasonable time if the spectrogram is fairly coarse. The system achieves a word error rate of 19% with a coarse spectrogram, while a system based on Hidden Markov Models achieves a word error rate of 15% on the same spectrograms. / Thesis (PhD)--University of Pretoria, 2008. / Electrical, Electronic and Computer Engineering / unrestricted

We study how to perform effective Bayesian inference in high-dimensional sparse Factor Analysis models with a zero-norm, sparsity-inducing prior on the model parameters. Such priors represent a methodological ideal, but Bayesian inference in such models is usually regarded as impractical. We test this view. After empirically characterising the properties of existing algorithmic approaches, we use techniques from statistical mechanics to derive a theory of optimal learning in the restricted setting of sparse PCA with a single factor. Finally, we describe a novel `Dense Message Passing' algorithm (DMP) which achieves near-optimal performance on synthetic data generated from this model.DMP exploits properties of high-dimensional problems to operate successfully on a densely connected graphical model. Similar algorithms have been developed in the statistical physics community and previously applied to inference problems in coding and sparse classification. We demonstrate that DMP out-performs both a newly proposed variational hybrid algorithm and two other recently published algorithms (SPCA and emPCA) on synthetic data while it explains at least the same amount of variance, for a given level of sparsity, in two gene expression datasets used in previous studies of sparse PCA.A significant potential advantage of DMP is that it provides an estimate of the marginal likelihood which can be used for hyperparameter optimisation. We show that, for the single factor case, this estimate exhibits good qualitative agreement both with theoretical predictions and with the hyperparameter posterior inferred by a collapsed Gibbs sampler. Preliminary work on an extension to inference of multiple factors indicates its potential for selecting an optimal model from amongst candidates which differ both in numbers of factors and their levels of sparsity.

No description available.

Program checking is indisputably important, especially if originating in formal methods. VeriFIT at FIT BUT uses custom Code Listener (CL) infrastructure modularly interconnecting the front-end, typically a code parser adapter, and the back-end, typically an analyser. Our aim is to offer a former as a compact alternative to existing GCC compiler plug-in. This adapter uses linearized code mediated by sparse library for static analysis of programs in C. According to the experiments with one of the main CL analysers, Predator tool and its tests suite, our product - clsp program - is successful successful in roughly 75% of cases in comparison with the GCC plug-in. Further improvements are expected.

In this thesis, the red hot topic anomaly detection is studied, which is a subtopic in machine learning. The company, Procera Networks, supports several broadband companies with IT-solutions and would like to detected errors in these systems automatically. This thesis investigates and devises methods and algorithms for detecting interesting events in diagnostics data. Events of interest include: short-term deviations (a deviating point), long-term deviations (a distinct trend) and other unexpected deviations. Three models are analyzed, namely Linear Predictive Coding, Sparse Linear Prediction and Wavelet Transformation. The final outcome is determined by the gap to certain thresholds. These thresholds are customized to fit the model as well as possible. / I den här rapporten kommer det glödheta området anomalidetektering studeras, vilket tillhör ämnet Machine Learning. Företaget där arbetet utfördes på heter Procera Networks och jobbar med IT-lösningar inom bredband till andra företag. Procera önskar att kunna upptäcka fel hos kunderna i dessa system automatiskt. I det här projektet kommer olika metoder för att hitta intressanta företeelser i datatraffiken att genomföras och forskas kring. De mest intressanta företeelserna är framfärallt snabba avvikelser (avvikande punkt) och färändringar äver tid (trender) men också andra oväntade mänster. Tre modeller har analyserats, nämligen Linear Predictive Coding, Sparse Linear Prediction och Wavelet Transform. Det slutgiltiga resultatet från modellerna är grundat på en speciell träskel som är skapad fär att ge ett så bra resultat som mäjligt till den undersäkta modellen..