1,721,024 research outputs found
Incomplete factorization preconditioning for linear least squares problems
No full textA new family of preconditioners for conjugate gradient-like iterative methods applied to large sparse linear least squares problems, min\Vert Ax-b\Vert\sb2, is proposed. The family is based on incomplete Gram-Schmidt (IGS) factorizations of A. Particular attention has been given to the following members of the family: Incomplete Classical Gram-Schmidt (ICGS), Incomplete Modified Gram-Schmidt (IMGS) and Compressed Incomplete Modified Gram-Schmidt (CIMGS) factorizations. The numerical properties of each of these methods have been considered as well as the relationships between the methods concerning the preservation of sparsity, computational efficiency and the quality of the preconditioner. The implementation of these methods has been investigated and all of the important family members have been coded. One of the important topics in this portion of the dissertation is the careful symbolic analysis of the production of the preconditioner and its use during the incomplete factorization phase to avoid excessive unnecessary work.We have also analyzed some of the implications of viewing the incomplete Cholesky (IC) factorization as a limit case of the IGS family. When certain conditions are imposed on the sparsity pattern of the preconditioning matrix, IC is identical to IMGS. Therefore, a sufficient condition on the sparsity pattern for a stable IC factorization can be derived. Based on this condition, two algorithms for modifying a sparsity pattern for which IC may not succeed have been designed. The altered IC method with the pattern modifications (ICPM) has been studied and its performance evaluated. These methods differ from previously proposed methods to guarantee the existence and improve the stability of the IC factorization since they do not require numerical information. Of course, for a particular matrix we can then use numerical information in addition to the pattern modification techniques to further improve the preconditioner.Numerical experiments illustrating the capabilities of the preconditioners are also presented. These include matrices from the standard Harwell-Boeing collection and various test matrices from different practical application problems.Made available in DSpace on 2011-05-07T12:34:44Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9416449.pdf: 9718058 bytes, checksum: 2043dcae7c5a89a8858c938e71b767e3 (MD5)
Previous issue date: 1994Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T14:42:50Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:18:40-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionETDs are only available to UIUC Users without author permissionU of I Onl
High-performance algorithms to solve Toeplitz and block Toeplitz matrices
No full textFast algorithms to factor Toeplitz matrices have existed since the beginning of this century. The two most notable algorithms to factor Toeplitz matrices are the Schur and the Levinson-Durbin. The former factors the Toeolitz matrix itself while the latter factors the inverse. In this thesis, we present several high performance variants of the classical Schur algorithm to factor various Toeplitz matrices. For positive definite block Toeplitz matrices, we show how hyperbolic Householder transformations may be blocked to yield a block Schur algorithm. This algorithm uses BLAS3 primitives and makes efficient use of a memory hierarchy. We present three algorithms for indefinite Toeplitz matrices. Two of these are based on look-ahead strategies and produce an exact factorization of the Toeplitz matrix. The third produces an inexact factorization via perturbations of singular principal minors. We also present an analysis of the numerical behavior of the third algorithm and derive a bound for the number of iterations to improve the accuracy of the solution. Recently, there have been several algorithms suggested to incorporate pivoting into the factorization of indefinite Toeplitz matrices by converting them to Cauchy-like matrices. We compare these algorithms from a computational standpoint and suggest a few algorithms that exploit properties such as realness and symmetry in the Toeplitz matrix while converting them to Cauchy-like matrices. In particular, we show how a Hermitian Toeplitz matrix may be converted to a real symmetric Cauchy-like matrix prior to factorization, yielding substantial savings in computation. For rank-deficient Toeplitz least-squares problems, we present a variant of the generalized Schur algorithm that avoids breakdown due to an exact rank deficiency. In the presence of a near rank deficiency, an approximate rank factorization of the Toeplitz matrix is produced. Algorithms to solve real Toeplitz least-squares problems and to obtain rank-revealing QR factorizations of real Toeplitz matrices are also presented. We demonstrate the use of the Schur algorithm in the construction of preconditioners to solve the problem of image deconvolution.Made available in DSpace on 2011-05-07T14:19:06Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9702684.pdf: 7078789 bytes, checksum: fb5278808ad15e6c4bd14079fa938f5d (MD5)
Previous issue date: 1996Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T15:05:22Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:31:19-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionETDs are only available to UIUC Users without author permissionU of I Onl
A family of preconditioned iterative solvers for sparse linear systems
No full textBased on the relationship between the family of Broyden methods and the EN method, a new family of iterative methods, the family of EN-like methods, is developed and analyzed. These methods are shown to be related to a variety of other known methods, which comprise the Broyden methods, GCR, GMRES, Newton's method for approximating the inverse, and a combination of a Galerkin step followed by a step of Richardson's method. Scaling-invariant versions and implementations of higher efficiency are developed, and their complexity is examined. The convergence of the new methods, as well as their restarted and truncated versions, are examined. Various convergence results are derived, which include termination within a finite number of steps and estimates for residuals and errors. The methods are also shown to be suitable in the context of inner/outer iteration schemes, and, for two of the methods, orthogonality preserving inner/outer iteration schemes are developed. Adaptive versions, which are a combination of truncated and restarted versions, and which automatically increase the size of the Krylov subspace, are included in the software package PARASPAR, which achieves robustness by reevaluating a parametrized preconditioner whenever poor convergence or instability is encountered. We present numerical experiments that demonstrate the efficiency of several members of this new family in comparison with other known methods, in the context of PARASPAR, and in the context of inner/outer iteration schemes. The experiments show that even though methods like CGS and BiCGSTAB may converge faster for many problems, EN-like methods are in general more robust, since, like GMRES, they have the option of increasing the size of the Krylov subspace. Additionally, they often require less memory than GMRES or ORTHOMIN. They are also very suitable as iterative solvers inside PARASPAR, since they evaluate, without additional cost, parameters that estimate the quality of the preconditioner. Some EN-like methods also show drastic divergence when applied to an ill-conditioned problem. Consequently, it is possible to quickly recognize when to reevaluate the preconditioner. Finally, nonlinear EN-like methods are developed, and their convergence behavior is investigated.Made available in DSpace on 2011-05-07T13:24:06Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9543780.pdf: 4387358 bytes, checksum: 52d1b8c71dcd24b46660729159037fd0 (MD5)
Previous issue date: 1995Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T14:54:17Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:25:12-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionETDs are only available to UIUC Users without author permissionU of I Onl
Portable relaxation-based circuit simulation on MIMD machines
No full textParallel CAD programs have been extensively reported in the literature. Unfortunately, they are not widely used in industry. One reason for this lack of use is that they are usually developed for a specific machine and are not easily ported to other parallel machines. While code portability is straightforward, the issue of performance portability is a rather difficult one to resolve. This dissertation attempts to bridge the gap between code portability and performance portability for a numerically intensive application program, specifically circuit simulation. Waveform relaxation is an effective algorithm to simulate large digital circuits designed today and is used as the main simulation algorithm. The parallel processing issues under investigation include circuit partitioning, task granularity modification, scheduling and allocation. The difficulty of addressing these issues by using generic parallel processing techniques is that circuit simulation problems tend to have highly irregular computational structures. The use of high-level waveforms generated from logic or timing simulators is introduced as a way of improving both speed and performance portability. Speedups of three to ten have been achieved using a combination of high-level information and event-driven waveform relaxation on eight processors as compared to the sequential program. Based on the knowledge acquired during the course of this research, an advanced framework for portable parallel circuit simulation is proposed. By taking the machine characteristics and the input stimuli into consideration, this research serves as a major step forward in performance portability.Made available in DSpace on 2011-05-07T11:58:20Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9512593.pdf: 8776897 bytes, checksum: bff134da1e90f4460727bdff907ef77e (MD5)
Previous issue date: 1994Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T14:34:58Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:13:36-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionETDs are only available to UIUC Users without author permissionU of I Onl
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Recommended from our members
A Performance Analysis of the Berkeley UPC Compiler
Get PDFUnified Parallel C (UPC) is a parallel language that uses a Single Program Multiple Data (SPMD) model of parallelism within a global address space. The global address space is used to simplify programming, especially on applications with irregular data structures that lead to fine-grained sharing between threads. Recent results have shown that the performance of UPC using a commercial compiler is comparable to that of MPI [7]. In this paper we describe a portable open source compiler for UPC. Our goal is to achieve a similar performance while enabling easy porting of the compiler and runtime, and also provide a framework that allows for extensive optimizations. We identify some of the challenges in compiling UPC and use a combination of micro-benchmarks and application kernels to show that our compiler has low overhead for basic operations on shared data and is competitive, and sometimes faster than, the commercial HP compiler. We also investigate several communication optimizations, and show significant benefits by hand-optimizing the generated code
Parallel Circuit Simulation Techniques for a Hierarchical Machine
No full textCircuit simulation remains an indispensable tool in the CAD community and is used widely to verify circuit functionality and to generate detailed timing information. As circuit designers push the limits on chip density and complexity, more powerful parallel processing resources and more efficient techniques are needed to speed up the simulation process. This dissertation addresses some general issues in parallel circuit simulation and investigates a variety of classical algorithms on the Cedar multiprocessor. Unfortunately, the range of behavior observed for these algorithms applied to various types of circuits is considerable. In an attempt to combine the advantages of several well-established algorithms, a hierarchical framework called CedarSim is proposed. This framework uses a hierarchical relaxation approach and allows different combinations of algorithms to be used at different levels. The objective is to allow each subcircuit to be solved using the most appropriate technique. This flexibility makes it possible to switch between standard and hierarchical algorithms to adapt to varying conditions. The proper functioning of this framework also hinges on appropriate circuit partitioning and effective algorithm selection, which are major research topics by themselves. This dissertation shows that, given proper mechanisms for these two tasks, CedarSim can deliver reasonable performance. This framework can also adapt to poor partitioning by using hierarchical relaxation and aggressive latency exploitation in several algorithms. Performance evaluation tools and techniques are used extensively to understand the behavior of the algorithms and the architecture and to study the interactions between various performance issues. Observations on the strengths and weaknesses of machines such as Cedar are also made. The knowledge acquired in this work also serves as a guideline for a more ambitious goal of developing a portable parallel circuit simulator.Made available in DSpace on 2014-12-16T22:23:18Z (GMT). No. of bitstreams: 1
9411660.pdf: 10005406 bytes, checksum: 1c589d6e707705550d388825c83fd1a4 (MD5)
Previous issue date: 1993Embargo set by: Seth Robbins for item 72178
Lift date: Forever
Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDsRestricted to the U of I community idenfinitely during batch ingest of legacy ETDsU of I Only211 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993
- …
