+publisher:"University of Colorado" +contributor:("Gunnar Martinsson")

University of Colorado

1. Young, Patrick McKendree. Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting.

Degree: PhD, Applied Mathematics, 2010, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/8

► Digital microfluidics is a rapidly growing field wherein droplets are manipulated for use in small-scale applications such as variable focus lenses, display technology, fiber… (more)

▼ Digital microfluidics is a rapidly growing field wherein droplets are manipulated for use in small-scale applications such as variable focus lenses, display technology, fiber optics, and lab-on-a-chip devices. There has been considerable interest in digital microfluidics and the various methods for liquid actuation by thermal, chemical, and electrical means, where each of the actuation methods make use of the favorable scaling relationship of surface tension forces at the micro scale. Another increasingly important field is addressing the ever growing need for improved heat transfer techniques in the next generation of electronic devices. As device size decreases and device efficiency increases, high heat flux removal capabilities (100 - 1000 W/cm2) are critical to achieve the lower device operating temperatures necessary to ensure reliably and performance. In this thesis, we investigate the nature of the forcing that occurs in the transport of liquid drops by electrical means. The effects of system parameters on the force density and its net integral are considered in the case of dielectrophoresis (insulating fluids) and electrowetting-on-dielectric (conductive fluids). Moreover, we explore the effectiveness of a new heat transfer technique called digitized heat transfer (DHT), where droplets are utilized to enhance the removal of heat from electronic devices. Numerical computations of the Nusselt number for these types of flows provide strong evidence of the effectiveness of DHT in comparison to continuous flows. These two physical phenomena are but two examples that illustrate the growing need for numerical techniques that simply and efficiently handle problems on irregular domains. We present two algorithms appropriate in this environment. The first extends the recently introduced Immersed Boundary Projection Method (IBPM), originally developed for the incompressible Navier-Stokes equations, to elliptic and parabolic problems on irregular domains in a second-order accurate manner. The second algorithm employs a boundary integral approach to the solution of elliptic problems in three-dimensional axisymmetric domains with non-axisymmetric boundary conditions. By using Fourier transforms to reduce the three-dimensional problem to a series of problems defined on the generating curve of the surface, a Nyström discretization employing generalized Gaussian quadratures can be applied to rapidly compute the solution with high accuracy. We demonstrate the high order nature of the discretization. An accelerated technique for computing the kernels of the reduced integral equations is developed for those kernels arising from Laplace's equation, overcoming what was previously the major obstacle in the solution to such problems. We extend this technique to a wide class of kernels, with a particular emphasis on those arising from the Helmholtz equation, and provide strong numerical evidence of the efficiency of this approach. By combining the above approach with the Fast Multipole Method, we develop an… Advisors/Committee Members: Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Kamran Mohseni, Thomas Manteuffel.

Subjects/Keywords: Dielectrophoresis; Digital Microfluidics; Digitized Heat Transfer; Electrowetting; Immersed Boundary Methods; Integral Equations; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Young, P. M. (2010). Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/8

Chicago Manual of Style (16^th Edition):

Young, Patrick McKendree. “Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting.” 2010. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/8.

MLA Handbook (7^th Edition):

Young, Patrick McKendree. “Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting.” 2010. Web. 07 Mar 2021.

Vancouver:

Young PM. Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting. [Internet] [Doctoral dissertation]. University of Colorado; 2010. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/8.

Council of Science Editors:

Young PM. Numerical Techniques for the Solution of Partial Differential and Integral Equations on Irregular Domains with Applications to Problems in Electrowetting. [Doctoral Dissertation]. University of Colorado; 2010. Available from: https://scholar.colorado.edu/appm_gradetds/8

University of Colorado

2. Gillman, Adrianna. Fast Direct Solvers for Elliptic Partial Differential Equations.

Degree: PhD, Applied Mathematics, 2011, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/20

► The dissertation describes fast, robust, and highly accurate numerical methods for solving boundary value problems associated with elliptic PDEs such as Laplace's and Helmholtz'… (more)

▼ The dissertation describes fast, robust, and highly accurate numerical methods for solving boundary value problems associated with elliptic PDEs such as Laplace's and Helmholtz' equations, the equations of elasticity, and time-harmonic Maxwell's equation. In many areas of science and engineering, the cost of solving such problems determines what can and cannot be modeled computationally. Elliptic boundary value problems may be solved either via discretization of the PDE (e.g., finite element methods) or by first reformulating the equation as an integral equation, and then discretizing the integral equation. In either case, one is left with the task of solving a system of linear algebraic equations that could be very large. There exist a broad range of schemes with linear complexity for solving these equations (multigrid, preconditioned Krylov methods, etc). Most of these schemes are based on ``iterative'' techniques that build a sequence of approximate solutions that converges to the exact solution. In contrast, the methods described here are ``direct'' in the sense that they construct an approximation to the inverse (or LU/Cholesky factorization) of the coefficient matrix. Such direct solvers tend to be more robust, versatile, and stable than iterative methods, but have until recently been considered prohibitively expensive for large scale problems. The objective of the dissertation is to demonstrate that in important environments it is possible to construct an approximate inverse with linear computational cost. The methods are for a single solve competitive with the best iterative methods, and can be far faster than any previously available methods in situations where the same coefficient matrix is used in a sequence of problems. In addition, a new discretization technique for elliptic boundary value problems is proposed. The idea is to first compute the solution operator of a large collection of small domains. The small domains are chosen such that the operator is easily computed to high accuracy. A global equilibrium equation is then built by equating the fluxes through all internal domain boundaries. The resulting linear system is well-suited to the newly developed fast direct solvers. Advisors/Committee Members: Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Gregory Beylkin, Bradley Alpert.

Subjects/Keywords: Fast methods; Linear algebra; Numerical Analysis; Partial Differential Equations; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Gillman, A. (2011). Fast Direct Solvers for Elliptic Partial Differential Equations. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/20

Chicago Manual of Style (16^th Edition):

Gillman, Adrianna. “Fast Direct Solvers for Elliptic Partial Differential Equations.” 2011. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/20.

MLA Handbook (7^th Edition):

Gillman, Adrianna. “Fast Direct Solvers for Elliptic Partial Differential Equations.” 2011. Web. 07 Mar 2021.

Vancouver:

Gillman A. Fast Direct Solvers for Elliptic Partial Differential Equations. [Internet] [Doctoral dissertation]. University of Colorado; 2011. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/20.

Council of Science Editors:

Gillman A. Fast Direct Solvers for Elliptic Partial Differential Equations. [Doctoral Dissertation]. University of Colorado; 2011. Available from: https://scholar.colorado.edu/appm_gradetds/20

University of Colorado

3. Halko, Nathan P. Randomized Methods for Computing Low-Rank Approximations of Matrices.

Degree: PhD, Applied Mathematics, 2012, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/26

► Randomized sampling techniques have recently proved capable of efficiently solving many standard problems in linear algebra, and enabling computations at scales far larger than… (more)

▼ Randomized sampling techniques have recently proved capable of efficiently solving many standard problems in linear algebra, and enabling computations at scales far larger than what was previously possible. The new algorithms are designed from the bottom up to perform well in modern computing environments where the expense of communication is the primary constraint. In extreme cases, the algorithms can even be made to work in a streaming environment where the matrix is not stored at all, and each element can be seen only once. The dissertation describes a set of randomized techniques for rapidly constructing a low-rank ap- proximation to a matrix. The algorithms are presented in a modular framework that first computes an approximation to the range of the matrix via randomized sampling. Secondly, the matrix is pro- jected to the approximate range, and a factorization (SVD, QR, LU, etc.) of the resulting low-rank matrix is computed via variations of classical deterministic methods. Theoretical performance bounds are provided. Particular attention is given to very large scale computations where the matrix does not fit in RAM on a single workstation. Algorithms are developed for the case where the original matrix must be stored out-of-core but where the factors of the approximation fit in RAM. Numerical examples are provided that perform Principal Component Analysis of a data set that is so large that less than one hundredth of it can fit in the RAM of a standard laptop computer. Furthermore, the dissertation presents a parallelized randomized scheme for computing a reduced rank Singular Value Decomposition. By parallelizing and distributing both the randomized sampling stage and the processing of the factors in the approximate factorization, the method requires an amount of memory per node which is independent of both dimensions of the input matrix. Numerical experiments are performed on Hadoop clusters of computers in Amazon's Elastic Compute Cloud with up to 64 total cores. Finally, we directly compare the performance and accuracy of the randomized algorithm with the classical Lanczos method on extremely large, sparse matrices and substantiate the claim that randomized methods are superior in this environment. Advisors/Committee Members: Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Keith Julien, David M. Bortz.

Subjects/Keywords: hadoop; mahout; mapreduce; out of core; randomized sampling; singular value decomposition; Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Halko, N. P. (2012). Randomized Methods for Computing Low-Rank Approximations of Matrices. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/26

Chicago Manual of Style (16^th Edition):

Halko, Nathan P. “Randomized Methods for Computing Low-Rank Approximations of Matrices.” 2012. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/26.

MLA Handbook (7^th Edition):

Halko, Nathan P. “Randomized Methods for Computing Low-Rank Approximations of Matrices.” 2012. Web. 07 Mar 2021.

Vancouver:

Halko NP. Randomized Methods for Computing Low-Rank Approximations of Matrices. [Internet] [Doctoral dissertation]. University of Colorado; 2012. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/26.

Council of Science Editors:

Halko NP. Randomized Methods for Computing Low-Rank Approximations of Matrices. [Doctoral Dissertation]. University of Colorado; 2012. Available from: https://scholar.colorado.edu/appm_gradetds/26

University of Colorado

4. Folberth, James. Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing.

Degree: PhD, 2018, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/134

► In this dissertation we consider numerical methods for a problem in each of numerical linear algebra, digital signal processing, and image processing for super-resolution… (more)

▼ In this dissertation we consider numerical methods for a problem in each of numerical linear algebra, digital signal processing, and image processing for super-resolution fluorescence microscopy. We consider first a fast, randomized mixing operation applied to the unpivoted Householder QR factorization. The method is an adaptation of a slower randomized operation that is known to provide a rank-revealing factorization with high probability. We perform a number of experiments to highlight possible uses of our method and give evidence that our algorithm likely also provides a rank-revealing factorization with high probability. In the next chapter we develop fast algorithms for computing the discrete, narrowband cross-ambiguity function (CAF) on a downsampled grid of delay values for the purpose of quickly detecting the location of peaks in the CAF surface. Due to the likelihood of missing a narrow peak on a downsampled grid of delay values, we propose methods to make our algorithms robust against missing peaks. To identify peak locations to high accuracy, we propose a two-step approach: first identify a coarse peak location using one of our delay-decimated CAF algorithms, then compute the CAF on a fine, but very small, grid around the peak to find its precise location. Runtime experiments with our C++ implementations show that our delay-decimated algorithms can give more than an order of magnitude improvement in overall runtime to detect peaks in the CAF surface when compared against standard CAF algorithms. In the final chapter we study non-negative least-squares (NNLS) problems arising from a new technique in super-resolution fluorescence microscopy. The image formation task involves solving many tens of thousands of NNLS problems, each using the same matrix, but different right-hand sides. We take advantage of this special structure by adapting an optimal first-order method to efficiently solve many NNLS problems simultaneously. Our NNLS problems are extremely ill-conditioned, so we also experiment with using a block-diagonal preconditioner and the alternating direction method of multipliers (ADMM) to improve convergence speed. We also develop a safe feature elimination strategy for general NNLS problems. It eliminates features only when they are guaranteed to have weight zero at an optimal point. Our strategy is inspired by recent works in the literature for ℓ₁-regularized least-squares, but a notable exception is that we develop our method to use an inexact, but feasible, primal-dual point pair. This allows us to use feature elimination reliably on the extremely ill-conditioned NNLS problems from our microscopy application. For an example image reconstruction, we use our feature elimination strategy to certify that the reconstructed super-resolved image is unique. Advisors/Committee Members: Stephen Becker, Jed Brown, Ian Grooms, Christian Ketelsen, Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson.

Subjects/Keywords: cross-ambiguity function; duality; non-negative least-squares; qr factorization; image processing; Applied Mathematics; Applied Statistics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Folberth, J. (2018). Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/134

Chicago Manual of Style (16^th Edition):

Folberth, James. “Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing.” 2018. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/134.

MLA Handbook (7^th Edition):

Folberth, James. “Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing.” 2018. Web. 07 Mar 2021.

Vancouver:

Folberth J. Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing. [Internet] [Doctoral dissertation]. University of Colorado; 2018. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/134.

Council of Science Editors:

Folberth J. Fast and Reliable Methods in Numerical Linear Algebra, Signal Processing, and Image Processing. [Doctoral Dissertation]. University of Colorado; 2018. Available from: https://scholar.colorado.edu/appm_gradetds/134

University of Colorado

5. Babb, Tracy. Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems.

Degree: PhD, 2019, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/156

► The dissertation concerns numerical methods for approximately solving certain linear partial differential equations. The foundation is a solution methodology for linear elliptic boundary value… (more)

▼ The dissertation concerns numerical methods for approximately solving certain linear partial differential equations. The foundation is a solution methodology for linear elliptic boundary value problems that we call the ``Hierarchical Poincare-Steklov (HPS)'' method. This method is based on a high-order multidomain spectral discretization that is designed to work particularly well in conjunction with nested-dissection type direct solvers. The methods presented apply in any dimension, but their efficiency deteriorates as the dimension increases, and dimensions higher than three are generally not considered. A key competitive advantage of the HPS method is that the linear system that results from discretizing an elliptic PDE is solved using a direct rather than an iterative solver. This solver is closely related to existing nested dissection and multifrontal solvers, and has a similar computational profile that involves a ``build stage'' that is reasonably efficient, and then a ``solve stage'' that is very fast. This makes the method particularly powerful for use in situations where a sequence of linear problems involving the same operator needs to be solved, as happens for instance when solving certain parabolic and hyperbolic PDEs. The use of a direct solver also enables the method to solve many problems that are intractable to iterative solvers, such as Helmholtz problems at intermediate and high frequencies. The HPS methodology was originally published as a solution method for homogeneous elliptic problems, and the core contributions of the dissertation involve the extension of the methodology to more general environments. Specifically, there are four key contributions: 1. An extension of the method to handle non homogeneous elliptic equations that involve forcing terms in the volume of the domain. 2. A generalization of the method to allow the use of refined meshes in order to resolve local singularities. 3. An efficient solver for hyperbolic equations that works by applying the HPS methodology to explicitly build highly accurate approximations to the time evolution operator. This enables the use of very long time steps, and parallel in time implementations. 4. An efficient solver for parabolic problems, where the main idea is to accelerate implicit time-stepping schemes by using the HPS methodology to pre-compute the solution operator involved in the elliptic solve. This work also includes an extension to certain non-linear problems. All techniques presented are analyzed in terms of their complexity. Accuracy and stability are demonstrated via extensive numerical examples. Advisors/Committee Members: Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Daniel Appelo, Adrianna Gillman, Bengt Fornberg, Gregory Beylkin.

Subjects/Keywords: Poincare-steklov; linear partial differential equations; multidomain spectral discretization; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Babb, T. (2019). Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/156

Chicago Manual of Style (16^th Edition):

Babb, Tracy. “Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems.” 2019. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/156.

MLA Handbook (7^th Edition):

Babb, Tracy. “Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems.” 2019. Web. 07 Mar 2021.

Vancouver:

Babb T. Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems. [Internet] [Doctoral dissertation]. University of Colorado; 2019. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/156.

Council of Science Editors:

Babb T. Accelerated Time-Stepping of Parabolic and Hyperbolic Pdes Via Fast Direct Solvers for Elliptic Problems. [Doctoral Dissertation]. University of Colorado; 2019. Available from: https://scholar.colorado.edu/appm_gradetds/156

University of Colorado

6. Biagioni, David Joseph. Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations.

Degree: PhD, Applied Mathematics, 2012, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/29

► This thesis consists of two parts. In Part I, we describe an algorithm for approximating the Green's function for elliptic problems with variable coefficients… (more)

▼ This thesis consists of two parts. In Part I, we describe an algorithm for approximating the Green's function for elliptic problems with variable coefficients in arbitrary dimension. The basis for our approach is the separated representation, which appears as a way of approximating functions of many variables by sums of products of univariate functions. While the differential operator we wish to invert is typically ill-conditioned, its conditioning may be improved by first applying the Green's function for the constant coefficient problem. This function may be computed either numerically or, in some case, analytically in a separated format. The variable coefficient Green's function is then computed using a quadratically convergent iteration on the preconditioned operator, with sparsity maintained via representation in a wavelet basis. Of particular interest is that the method scales linearly in the number of dimensions, a feature that very desirable in high dimensional problems in which the curse of dimensionality must be reckoned with. As a corollary to this work, we described a randomized algorithm for maintaining low separation rank of the functions used in the construction of the Green's function. For certain functions of practical interest, one can avoid the cost of using standard methods such as alternating least squares (ALS) to reduce the separation rank. Instead, terms from the separated representation may be selected using a randomized approach based on matrix skeletonization and the interpolative decomposition. The use of random projections can greatly reduce the cost of rank reduction, as well as calculation of the Frobenius norm and term-wise Gram matrices. In Part II of the thesis, we highlight three practical applications of sparse and separable approximations to the analysis of renewable energy data. In the first application, error estimates gleaned from repeated measurements are incorporated into sparse regression algorithms (LASSO and the Dantzig selector) to minimize the statistical uncertainty of the resulting model. Applied to real biomass data, this approach leads to sparser regression coefficients corresponding to improved accuracy as measured by k-fold cross validation error. In the second application, a regression model based on separated representations is fit to reliability data for cadmium telluride (CdTe) thin-film solar cells. The data is inherently multi-way, and our approach avoids artificial matricization that would typically be performed for use with standard regression algorithms. Two distinct modes of degradation, corresponding to short- and long-term decrease in cell efficiency, are identified. In the third application, some theoretical properties of a popular chemometrics algorithm called orthogonal projections to latent structures (O-PLS) are derived. Advisors/Committee Members: Gregory Beylkin, Alireza Doostan, Peter Graf, Gunnar Martinsson, Keith Julien.

Subjects/Keywords: Curse of dimensionality; Direct Poisson solver; High dimensional partial differential equations; Numerical analysis; Randomized canonical tensor decomposition; Separated representations; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Biagioni, D. J. (2012). Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/29

Chicago Manual of Style (16^th Edition):

Biagioni, David Joseph. “Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations.” 2012. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/29.

MLA Handbook (7^th Edition):

Biagioni, David Joseph. “Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations.” 2012. Web. 07 Mar 2021.

Vancouver:

Biagioni DJ. Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations. [Internet] [Doctoral dissertation]. University of Colorado; 2012. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/29.

Council of Science Editors:

Biagioni DJ. Numerical construction of Green’s functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations. [Doctoral Dissertation]. University of Colorado; 2012. Available from: https://scholar.colorado.edu/appm_gradetds/29

University of Colorado

7. Reynolds, Matthew Jason. Nonlinear approximations in tomography, quadrature construction, and multivariate reductions.

Degree: PhD, Applied Mathematics, 2012, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/37

► This thesis consists of contributions to three topics: algorithms for computing generalized Gaussian quadratures, tomographic imaging algorithms, and reduction algorithms. Our approach is based… (more)

▼ This thesis consists of contributions to three topics: algorithms for computing generalized Gaussian quadratures, tomographic imaging algorithms, and reduction algorithms. Our approach is based on using non-linear approximations of functions. We develop a new algorithm for constructing generalized Gaussian quadratures for exponentials inte- grated against a non-sign-definite weight function. These quadratures integrate band-limited exponentials to a user-defined accuracy. We also introduce a method of computing quadrature weights via l∞ minimization. Second, we develop a new imaging algorithm for X-ray tomography. This algorithm, Polar Quadrature Inversion, uses rational approximations to approximate tomographic projections with a near optimal number of terms for a given accuracy. This rational signal model allows us to augment the measured data by extending the tomographic projection's domain in Fourier space. As the extended data from all the projections fill a disk in the Fourier domain, we use polar quadratures for band-limited exponentials and the Unequally Spaced Fast Fourier Transform to obtain our image. We demonstrate that the resulting images have significantly improved resolution without additional artifacts near sharp transitions. Finally, we develop an extension of existing reduction algorithms for functions of one variable to functions of many variables. By reduction, we understand an approximation (to a user-supplied accuracy) of a linear combination of decaying exponentials by a representation of the same form but with a minimal number of terms. While for functions of one variable there is an underlying theory based on the analysis of functions of one complex variable, no such theory is available for the multivariate case. Our approach is a first step in the development of such theory. We demonstrate our algorithm on two examples of multivariate functions, a suboptimal linear combination of real-valued, decaying exponentials, and that of complex-valued, decaying exponentials. Advisors/Committee Members: Gregory Beylkin, Gunnar Martinsson, Keith Julien, Francois Meyer, Rafael Peistun.

Subjects/Keywords: Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Reynolds, M. J. (2012). Nonlinear approximations in tomography, quadrature construction, and multivariate reductions. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/37

Chicago Manual of Style (16^th Edition):

Reynolds, Matthew Jason. “Nonlinear approximations in tomography, quadrature construction, and multivariate reductions.” 2012. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/37.

MLA Handbook (7^th Edition):

Reynolds, Matthew Jason. “Nonlinear approximations in tomography, quadrature construction, and multivariate reductions.” 2012. Web. 07 Mar 2021.

Vancouver:

Reynolds MJ. Nonlinear approximations in tomography, quadrature construction, and multivariate reductions. [Internet] [Doctoral dissertation]. University of Colorado; 2012. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/37.

Council of Science Editors:

Reynolds MJ. Nonlinear approximations in tomography, quadrature construction, and multivariate reductions. [Doctoral Dissertation]. University of Colorado; 2012. Available from: https://scholar.colorado.edu/appm_gradetds/37

University of Colorado

8. Lewis, Ryan D. Nonlinear Approximations in Filter Design and Wave Propagation.

Degree: PhD, Applied Mathematics, 2013, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/47

► This thesis has two parts. In both parts we use nonlinear approximations to obtain accurate solutions to problems where traditional numerical approaches rapidly become… (more)

▼ This thesis has two parts. In both parts we use nonlinear approximations to obtain accurate solutions to problems where traditional numerical approaches rapidly become computationally infeasible. The first part describes a systematic method for designing highly accurate and efficient infinite impulse response (IIR) and finite impulse response (FIR) filters given their specifications. In our approach, we first meet the specifications by constructing an IIR filter, without requiring the filter to be causal, and possibly with a large number of poles. We then construct, for any given accuracy, an optimal IIR version of such filter. Finally, also for any given accuracy, we convert the IIR filter to an efficient FIR filter cascade. In this FIR approximation, the non-causal part of the IIR filter only introduces an additional delay. Because our IIR construction does not have to enforce causality, the filters we design are more efficient than filters designed by existing methods. The second part describes a fast algorithm to propagate, for any desired accuracy, a time-harmonic electromagnetic field between two planes separated by free space. The analytic formulation of this problem (circa 1897) requires the evaluation of the Rayleigh-Sommerfeld integral. If the distance between the planes is small, this integral can be accurately evaluated in the Fourier domain; if the distance is large, it can be accurately approximated by asymptotic methods. The computational difficulties arise in the intermediate region where, in order to obtain an accurate solution, it is necessary to apply the oscillatory Rayleigh-Sommerfeld kernel as is. In our approach, we accurately approximate the kernel by a short sum of Gaussians with complex exponents and then efficiently apply the result to input data using the unequally spaced fast Fourier transform. The resulting algorithm has the same computational complexity as methods based on the Fresnel approximation. We demonstrate that while the Fresnel approximation may provide adequate accuracy near the optical axis, the accuracy deteriorates significantly away from the optical axis. In contrast, our method maintains controlled accuracy throughout the entire computational domain. Advisors/Committee Members: Gregory Beylkin, Bradley Alpert, Mark Ablowitz, Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Rafael Piestun.

Subjects/Keywords: approximation by Gaussians; digital filter design; optimal rational approximation; Rayleigh-Sommerfeld integral; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Lewis, R. D. (2013). Nonlinear Approximations in Filter Design and Wave Propagation. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/47

Chicago Manual of Style (16^th Edition):

Lewis, Ryan D. “Nonlinear Approximations in Filter Design and Wave Propagation.” 2013. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/47.

MLA Handbook (7^th Edition):

Lewis, Ryan D. “Nonlinear Approximations in Filter Design and Wave Propagation.” 2013. Web. 07 Mar 2021.

Vancouver:

Lewis RD. Nonlinear Approximations in Filter Design and Wave Propagation. [Internet] [Doctoral dissertation]. University of Colorado; 2013. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/47.

Council of Science Editors:

Lewis RD. Nonlinear Approximations in Filter Design and Wave Propagation. [Doctoral Dissertation]. University of Colorado; 2013. Available from: https://scholar.colorado.edu/appm_gradetds/47

University of Colorado

9. Martin, Bradley Pifer. Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces.

Degree: PhD, Applied Mathematics, 2016, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/79

► Traditional finite difference methods for solving the partial differential equations (PDEs) associated with wave and heat transport often perform poorly when used in domains… (more)

Subjects/Keywords: finite differences; heat equation; interfaces; mesh free; RBF; wave equation; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Martin, B. P. (2016). Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/79

Chicago Manual of Style (16^th Edition):

Martin, Bradley Pifer. “Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces.” 2016. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/79.

MLA Handbook (7^th Edition):

Martin, Bradley Pifer. “Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces.” 2016. Web. 07 Mar 2021.

Vancouver:

Martin BP. Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces. [Internet] [Doctoral dissertation]. University of Colorado; 2016. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/79.

Council of Science Editors:

Martin BP. Application of Rbf-Fd to Wave and Heat Transport Problems in Domains with Interfaces. [Doctoral Dissertation]. University of Colorado; 2016. Available from: https://scholar.colorado.edu/appm_gradetds/79

University of Colorado

10. Yang, Xinshuo. Reduction of Multivariate Mixtures and Its Applications.

Degree: PhD, 2018, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/106

► We consider a fast deterministic algorithm to identify the "best" linearly independent terms in multivariate mixtures and use them to compute an equivalent representation… (more)

▼ We consider a fast deterministic algorithm to identify the "best" linearly independent terms in multivariate mixtures and use them to compute an equivalent representation with fewer terms, up to user-selected accuracy. Our algorithm employs the well-known pivoted Cholesky decomposition of the Gram matrix constructed using terms of the mixture. Importantly, the multivariate mixtures do not have to be a separated representation of a function and complexity of the algorithm is independent of the number of variables (dimensions). The algorithm requires 𝒪(r²N) operations, where N is the initial number of terms in a multivariate mixture and r is the number of selected terms. Due to the condition number of the Gram matrix, the resulting accuracy is limited to about 1/2 digits of the used floating point arithmetic. We also consider two additional reduction algorithms for the same purpose. The first algorithm is based on orthogonalization of the multivariate mixture and have a similar performance as the approach based on Cholesky factorization. The second algorithm yields a better accuracy, but currently in high dimensions is only applicable to multivariate mixtures in a separated representation. We use the reduction algorithm to develop a new adaptive numerical method for solving differential and integral equations in quantum chemistry. We demonstrate the performance of this approach by solving the Hartree-Fock equations in two cases of small molecules. We also describe a number of initial applications of the reduction algorithm to solve partial differential and integral equations and to address several problems in data sciences. For data science applications in high dimensions we consider kernel density estimation (KDE) approach for constructing a probability density function (PDF) of a cloud of points, a far-field kernel summation method and the construction of equivalent sources for non-oscillatory kernels (used in both, computational physics and data science) and, finally, show how to use the reduction algorithm to produce seeds for subdividing a cloud of points into groups. Advisors/Committee Members: Gregory Beylkin, Bengt Fornberg, Zydrunas Gimbutas, Ian Grooms, Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson.

Subjects/Keywords: far-field summation in high dimensions; hartree-fock equations; integral equations; kernel density estimation; multivariate mixtures; reduction algorithms; Applied Mathematics; Theory and Algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Yang, X. (2018). Reduction of Multivariate Mixtures and Its Applications. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/106

Chicago Manual of Style (16^th Edition):

Yang, Xinshuo. “Reduction of Multivariate Mixtures and Its Applications.” 2018. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/106.

MLA Handbook (7^th Edition):

Yang, Xinshuo. “Reduction of Multivariate Mixtures and Its Applications.” 2018. Web. 07 Mar 2021.

Vancouver:

Yang X. Reduction of Multivariate Mixtures and Its Applications. [Internet] [Doctoral dissertation]. University of Colorado; 2018. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/106.

Council of Science Editors:

Yang X. Reduction of Multivariate Mixtures and Its Applications. [Doctoral Dissertation]. University of Colorado; 2018. Available from: https://scholar.colorado.edu/appm_gradetds/106

University of Colorado

11. Appelhans, David John. Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement.

Degree: PhD, Applied Mathematics, 2014, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/63

► In this thesis we propose a new algorithm for solving PDEs on massively parallel computers. The Nested Iteration Adaptive Mesh Refinement Range Decomposition (NI-AMRRD)… (more)

Subjects/Keywords: Adaptive Refinement; FOSLS; High Performance Computing; Nested Iteration; Parallel Algorithms; Range Decomposition; Applied Mathematics; Computer Sciences; Theory and Algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Appelhans, D. J. (2014). Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/63

Chicago Manual of Style (16^th Edition):

Appelhans, David John. “Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement.” 2014. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/63.

MLA Handbook (7^th Edition):

Appelhans, David John. “Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement.” 2014. Web. 07 Mar 2021.

Vancouver:

Appelhans DJ. Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement. [Internet] [Doctoral dissertation]. University of Colorado; 2014. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/63.

Council of Science Editors:

Appelhans DJ. Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement. [Doctoral Dissertation]. University of Colorado; 2014. Available from: https://scholar.colorado.edu/appm_gradetds/63

University of Colorado

12. Heavner, Nathan. Building Rank-Revealing Factorizations with Randomization.

Degree: PhD, 2019, University of Colorado

URL: https://scholar.colorado.edu/appm_gradetds/155

► This thesis describes a set of randomized algorithms for computing rank revealing factorizations of matrices. These algorithms are designed specifically to minimize the amount… (more)

▼ This thesis describes a set of randomized algorithms for computing rank revealing factorizations of matrices. These algorithms are designed specifically to minimize the amount of data movement required, which is essential to high practical performance on modern computing hardware. The work presented builds on existing randomized algorithms for computing low-rank approximations to matrices, but essentially ex- tends the range of applicability of these methods by allowing for the efficient decomposition of matrices of any numerical rank, including full rank matrices. In contrast, existing methods worked well only when the numerical rank was substantially smaller than the dimensions of the matrix. The thesis describes algorithms for computing two of the most popular rank-revealing matrix decom- positions: the column pivoted QR (CPQR) decomposition, and the so called UTV decomposition that factors a given matrix A as A = UTV∗, where U and V have orthonormal columns and T is triangular. For each algorithm, the thesis presents algorithms that are tailored for different computing environments, including multicore shared memory processors, GPUs, distributed memory machines, and matrices that are stored on hard drives (“out of core”). The first chapter of the thesis consists of an introduction that provides context, reviews previous work in the field, and summarizes the key contributions. Beside the introduction, the thesis contains six additional chapters: Chapter 2 introduces a fully blocked algorithm HQRRP for computing a QR factorization with col- umn pivoting. The key to the full blocking of the algorithm lies in using randomized projections to create a low dimensional sketch of the data, where multiple good pivot columns may be cheaply computed. Nu- merical experiments show that HQRRP is several times faster than the classical algorithm for computing a column pivoted QR on a multicore machine, and the acceleration factor increases with the number of cores. Chapter 3 introduces randUTV, a randomized algorithm for computing a rank-revealing factorization of the form A = UTV∗, where U and V are orthogonal and T is upper triangular. RandUTV uses random- ized methods to efficiently build U and V as approximations of the column and row spaces of A. The result is an algorithm that reveals rank nearly as well as the SVD and costs at most as much as a column pivoted QR. Chapter 4 provides optimized implementations for shared and distributed memory architectures. For shared memory, we show that formulating randUTV as an algorithm-by-blocks increases its efficiency in parallel. The fifth chapter implements randUTV on the GPU and augments the algorithm with an over- sampling technique to further increase the low rank approximation properties of the resulting factorization. Chapter 6 implements both randUTV and HQRRP for use with matrices stored out of core. It is shown that reorganizing HQRRP as a left-looking algorithm to reduce the number of writes to the drive is in the tested cases… Advisors/Committee Members: Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Stephen Becker, Gregory Beylkin, Gregorio Quintana-Ortí, Christian Ketelsen.

Subjects/Keywords: linear algebra; matrix factorizations; randomization; rank-revealing factorizations; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Heavner, N. (2019). Building Rank-Revealing Factorizations with Randomization. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/155

Chicago Manual of Style (16^th Edition):

Heavner, Nathan. “Building Rank-Revealing Factorizations with Randomization.” 2019. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/appm_gradetds/155.

MLA Handbook (7^th Edition):

Heavner, Nathan. “Building Rank-Revealing Factorizations with Randomization.” 2019. Web. 07 Mar 2021.

Vancouver:

Heavner N. Building Rank-Revealing Factorizations with Randomization. [Internet] [Doctoral dissertation]. University of Colorado; 2019. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/appm_gradetds/155.

Council of Science Editors:

Heavner N. Building Rank-Revealing Factorizations with Randomization. [Doctoral Dissertation]. University of Colorado; 2019. Available from: https://scholar.colorado.edu/appm_gradetds/155

University of Colorado

13. Kaslovsky, Daniel N. Geometric Sparsity in High Dimension.

Degree: PhD, Mathematics, 2012, University of Colorado

URL: https://scholar.colorado.edu/math_gradetds/15

► While typically complex and high-dimensional, modern data sets often have a concise underlying structure. This thesis explores the sparsity inherent in the geometric structure… (more)

▼ While typically complex and high-dimensional, modern data sets often have a concise underlying structure. This thesis explores the sparsity inherent in the geometric structure of many high-dimensional data sets. Constructing an efficient parametrization of a large data set of points lying close to a smooth manifold in high dimension remains a fundamental problem. One approach, guided by geometry, consists in recovering a local parametrization (a chart) using the local tangent plane. In practice, the data are noisy and the estimation of a low-dimensional tangent plane in high dimension becomes ill posed. Principal component analysis (PCA) is often the tool of choice, as it returns an optimal basis in the case of noise-free samples from a linear subspace. To process noisy data, PCA must be applied locally, at a scale small enough such that the manifold is approximately linear, but at a scale large enough such that structure may be discerned from noise. We present an approach that uses the geometry of the data to guide our definition of locality, discovering the optimal balance of this noise-curvature trade-off. Using eigenspace perturbation theory, we study the stability of the subspace estimated by PCA as a function of scale, and bound (with high probability) the angle it forms with the true tangent space. By adaptively selecting the scale that minimizes this bound, our analysis reveals the optimal scale for local tangent plane recovery. Additionally, we are able to accurately and efficiently estimate the curvature of the local neighborhood, and we introduce a geometric uncertainty principle quantifying the limits of noise-curvature perturbation for tangent plane recovery. An algorithm for partitioning a noisy data set is then studied, yielding an appropriate scale for practical tangent plane estimation. Next, we study the interaction of sparsity, scale, and noise from a signal decomposition perspective. Empirical Mode Decomposition is a time-frequency analysis tool for nonstationary data that adaptively defines modes based on the intrinsic frequency scales of a signal. A novel understanding of the scales at which noise corrupts the otherwise sparse frequency decomposition is presented. The thesis concludes with a discussion of future work, including applications to image processing and the continued development of sparse representation from a geometric perspective. Advisors/Committee Members: Francois G. Meyer, James H. Curry, Gunnar%20Martinsson%22%29&pagesize-30">Per-Gunnar Martinsson, Gregory Beylkin, Thomas Manteuffel.

Subjects/Keywords: Geometry; High-dimensional data; Noise; Sparsity; Applied Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Kaslovsky, D. N. (2012). Geometric Sparsity in High Dimension. (Doctoral Dissertation). University of Colorado. Retrieved from https://scholar.colorado.edu/math_gradetds/15

Chicago Manual of Style (16^th Edition):

Kaslovsky, Daniel N. “Geometric Sparsity in High Dimension.” 2012. Doctoral Dissertation, University of Colorado. Accessed March 07, 2021. https://scholar.colorado.edu/math_gradetds/15.

MLA Handbook (7^th Edition):

Kaslovsky, Daniel N. “Geometric Sparsity in High Dimension.” 2012. Web. 07 Mar 2021.

Vancouver:

Kaslovsky DN. Geometric Sparsity in High Dimension. [Internet] [Doctoral dissertation]. University of Colorado; 2012. [cited 2021 Mar 07]. Available from: https://scholar.colorado.edu/math_gradetds/15.

Council of Science Editors:

Kaslovsky DN. Geometric Sparsity in High Dimension. [Doctoral Dissertation]. University of Colorado; 2012. Available from: https://scholar.colorado.edu/math_gradetds/15

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations