Thesis (M.S.)--University of Texas at El Paso, 2009. / Title from title screen. Vita. CD-ROM. Includes bibliographical references. Also available online.

Thesis (Ph.D.) - Carleton University, 2007. / Includes bibliographical references (p. 261-266). Also available in electronic format on the Internet.

Thesis (M.S.)--Rochester Institute of Technology, 2009. / Typescript. Includes bibliographical references (leaves

Existing Global Data Computation (GDC) protocols for asynchronous systems are designed for fully connected networks. In this paper, we discuss GDC in a dedicated asynchronous chordal ring, a type of un-fully connected networks. The virtual links approach, which constructs t+1 (t<n) process-disjoint paths for each pair of processes without direct connection to tolerate failures (where t is the maximum number of processes that may crash and n is the total number of processes), can be applied to solve the GDC problem in the chordal but the virtual links approach incurs high message complexity. To reduce the high communication cost, we propose a non round-based GDC protocol for the asynchronous chordal ring with perfect failure detectors. The main advantage of our approach is that there is no notion of round, processes only send messages via direct connections and the implementation of failure detectors does not require process-disjoint paths. Analysis and comparison with the virtual links approach shows that our protocol reduces the message complexity significantly. / Singapore-MIT Alliance (SMA)

Thesis (M.Sc.Eng.) PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you. / This thesis considers the efficient Hessian computation in inverse problems with specific application to the elastography inverse problem. Inverse problems use measurements of observable parameters to infer information about model parameters, and tend to be ill-posed. They are typically formulated and solved as regularized constrained optimization problems, whose solutions best fit the measured data. Approaching the same inverse problem from a probabilistic Bayesian perspective produces the same optimal point called the maximum a posterior (MAP) estimate of the parameter distribution, but also produces a posterior probability distribution of the parameter estimate, from which a measure of the solution's uncertainty may be obtained. This probability distribution is a very high dimensional function with which it can be difficult to work. For example, in a modest application with N = 104 optimization variables, representing this function with just three values in each direction requires 3^10000 U+2248 10^5000 variables, which far exceeds the number of atoms in the universe. The uncertainty of the MAP estimate describes the shape of the probability distribution and to leading order may be parameterized by the covariance. Directly calculating the Hessian and hence the covariance, requires O(N) solutions of the constraint equations. Given the size of the problems of interest (N = O(10^4 - 10^6)), this is impractical. Instead, an accurate approximation of the Hessian can be assembled using a Krylov basis. The ill-posed nature of inverse problems suggests that its Hessian has low rank and therefore can be approximated with relatively few Krylov vectors. This thesis proposes a method to calculate this Krylov basis in the process of determining the MAP estimate of the parameter distribution. Using the Krylov space based conjugate gradient (CG) method, the MAP estimate is computed. Minor modifications to the algorithm permit storage of the Krylov approximation of the Hessian. As the accuracy of the Hessian approximation is directly related to the Krylov basis, long term orthogonality amongst the basis vectors is maintained via full reorthogonalization. Upon reaching the MAP estimate, the method produces a low rank approximation of the Hessian that can be used to compute the covariance. / 2031-01-01

The need for graph computations is evident in a multitude of use cases. To support computations on large-scale graphs, several parallel systems have been developed. However, existing graph systems require users to recast algorithms into new models, which makes parallel graph computations as a privilege to experienced users only. Moreover, real world applications often require much more complex graph processing workflows than previously evaluated. In response to these challenges, the thesis presents GRAPE, a distributed graph computation system, shipped with various applications for social network analysis, social media marketing and functional dependencies on graphs. Firstly, the thesis presents the foundation of GRAPE. The principled approach of GRAPE is based on partial evaluation and incremental computation. Sequential graph algorithms can be plugged into GRAPE with minor changes, and get parallelized as a whole. The termination and correctness are guaranteed under a monotonic condition. Secondly, as an application on GRAPE, the thesis proposes graph-pattern association rules (GPARs) for social media marketing. GPARs help users discover regularities between entities in social graphs and identify potential customers by exploring social influence. The thesis studies the problem of discovering top-k diversified GPARs and the problem of identifying potential customers with GPARs. Although both are NP- hard, parallel scalable algorithms on GRAPE are developed, which guarantee a polynomial speedup over sequential algorithms with the increase of processors. Thirdly, the thesis proposes quantified graph patterns (QGPs), an extension of graph patterns by supporting simple counting quantifiers on edges. QGPs naturally express universal and existential quantification, numeric and ratio aggregates, as well as negation. The thesis proves that the matching problem of QGPs remains NP-complete in the absence of negation, and is DP-complete for general QGPs. In addition, the thesis introduces quantified graph association rules defined with QGPs, to identify potential customers in social media marketing. Finally, to address the issue of data consistency, the thesis proposes a class of functional dependencies for graphs, referred to as GFDs. GFDs capture both attribute-value dependencies and topological structures of entities. The satisfiability and implication problems for GFDs are studied and proved to be coNP-complete and NP-complete, respectively. The thesis also proves that the validation problem for GFDs is coNP- complete. The parallel algorithms developed on GRAPE verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs.

abstract: Distributed wireless sensor networks (WSNs) have attracted researchers recently due to their advantages such as low power consumption, scalability and robustness to link failures. In sensor networks with no fusion center, consensus is a process where all the sensors in the network achieve global agreement using only local transmissions. In this dissertation, several consensus and consensus-based algorithms in WSNs are studied. Firstly, a distributed consensus algorithm for estimating the maximum and minimum value of the initial measurements in a sensor network in the presence of communication noise is proposed. In the proposed algorithm, a soft-max approximation together with a non-linear average consensus algorithm is used. A design parameter controls the trade-off between the soft-max error and convergence speed. An analysis of this trade-off gives guidelines towards how to choose the design parameter for the max estimate. It is also shown that if some prior knowledge of the initial measurements is available, the consensus process can be accelerated. Secondly, a distributed system size estimation algorithm is proposed. The proposed algorithm is based on distributed average consensus and L2 norm estimation. Different sources of error are explicitly discussed, and the distribution of the final estimate is derived. The CRBs for system size estimator with average and max consensus strategies are also considered, and different consensus based system size estimation approaches are compared. Then, a consensus-based network center and radius estimation algorithm is described. The center localization problem is formulated as a convex optimization problem with a summation form by using soft-max approximation with exponential functions. Distributed optimization methods such as stochastic gradient descent and diffusion adaptation are used to estimate the center. Then, max consensus is used to compute the radius of the network area. Finally, two average consensus based distributed estimation algorithms are introduced: distributed degree distribution estimation algorithm and algorithm for tracking the dynamics of the desired parameter. Simulation results for all proposed algorithms are provided. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2017

Orientadores: Fernando José Von Zuben, Leandro Nunes de Castro Silva / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-22T19:55:45Z (GMT). No. of bitstreams: 1 Pasti_Rodrigo_D.pdf: 4931504 bytes, checksum: 28f0e5bc0f2210db1cfb2cd2fc4c7f15 (MD5) Previous issue date: 2013 / Resumo: Existem muitas formas de se entender e descrever a natureza, sendo que a Computação Natural parte do princípio de que sistemas naturais são processadores de informação, ou seja, realizam computação. Esta tese recorre aos mecanismos da Computação Natural para o entendimento das computações realizadas em um sistema natural específico: os ecossistemas. O primeiro passo está fundamentado na ciência da Biogeografia, que estuda os ecossistemas e seus padrões emergentes. Na Biogeografia, é possível identificar elementos, relações entre eles e processos. A principal contribuição desta tese está na formalização computacional da Biogeografia, dando origem à Computação Biogeográfica. A proposta da Computação Biogeográfica é desenvolvida em várias frentes. A primeira delas promove a formalização do metamodelo, definido como uma estrutura conceitual que busca contextualizar a existência de ecossistemas artificiais e seus processos espaço temporais. Em seguida, para ilustrar a aplicação do metamodelo, são propostas definições de computação de ecossistemas em superfícies adaptativas fenotípicas. Essas definições resultam em um conjunto de relações e processos, os quais são aplicáveis à construção de ecossistemas artificiais. Estes, por sua vez, permitem o entendimento de dinâmicas e padrões de ecossistemas e também podem contribuir para a resolução de problemas computáveis. Na etapa final da tese, será proposto um algoritmo de radiação adaptativa que exibe padrões similares aos encontrados em ecossistemas reais e que se mostra competitivo para otimização multimodal em espaços contínuos. Por fim, perspectivas futuras são apresentadas visando indicar caminhos para se consolidar a Computação Biogeográfica como um novo ramo da Computação Natural / Abstract: There are several attempts to understand and describe nature, and Natural Computing is founded on the principle that natural systems are information processors, in the sense that they perform computation. This thesis makes use of Natural Computing mechanisms for the understanding of the computation taking place in a specific natural system: the ecosystems. The first step is based on the science of Biogeography, devoted to the study of ecosystems and their emerging patterns. In Biogeography, it is possible to identify elements, relations among them, and processes. The main contribution of this thesis resides in the computational formalization of Biogeography, thus establishing the research area of Biogeographic Computation. The proposal of Biogeographic Computation is introduced in several fronts. The first front promotes the metamodel formalism, which defines a conceptual framework focused on contextualizing the existence of artificial ecosystems and their spatio-temporal processes. After that, aiming at illustrating the application of the metamodel, definitions of ecosystems computing in phenotypic adaptive surfaces is proposed. These definitions proceed to a set of relations and processes directly applicable to the proposition of artificial ecosystems. These artificial ecosystems promote the understanding of natural ecosystems dynamics and patterns, and can also contribute to the resolution of computable problems. At the final stage of the thesis, it is presented an adaptive radiation algorithm exhibiting patterns which are similar to the ones found in real ecosystems, and also proving to be competitive for multimodal optimization in continuous spaces. To conclude, some perspectives for the further steps of the research are outlined with the purpose of indicating some routes to consolidate Biogeographic Computation as a new branch of Natural Computing / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Computational design is often depicted as an instrument for analysis or production, but it is also a space in which to explore and create new ways of working and thinking. This thesis explores how, through critically engaged practice, designers working computationally are uniquely able to envision and work toward desirable futures, challenging a techno-utopian status quo and projecting humane alternatives. What computational design methods, approaches, and strategies can help to bring about these desirable futures? Through primary research involving interviews with computational design practitioners, developing interactive software prototypes as investigative tools, and conducting design workshops, I investigate various modes of working computationally. Building on this research, I propose a three-part framework that synthesizes high-level approaches to computational design work. The first component, generating, reveals how computation enables the designer to work at various levels of abstraction, navigating large possibility spaces. The second, simulating, provides a frame for envisioning and modeling potential interventions in complex systems. Finally, interrogating, drawing from both Schön’s ‘reflective practice’ and Wark’s ‘hacker ethos,’ encourages computational designers to critically question their tools and practices in order to discover new ways of working and thinking. I conclude by discussing potential embodiments of this framework in computational design education.

No description available.