Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Theory and Algorithms
Randomized Algorithms For Preconditioner Selection With Applications To Kernel Regression, Conner Dipaolo
Randomized Algorithms For Preconditioner Selection With Applications To Kernel Regression, Conner Dipaolo
HMC Senior Theses
The task of choosing a preconditioner M to use when solving a linear system Ax=b with iterative methods is often tedious and most methods remain ad-hoc. This thesis presents a randomized algorithm to make this chore less painful through use of randomized algorithms for estimating traces. In particular, we show that the preconditioner stability || I - M-1A ||F, known to forecast preconditioner quality, can be computed in the time it takes to run a constant number of iterations of conjugate gradients through use of sketching methods. This is in spite of folklore which …
Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott
Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott
HMC Senior Theses
Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe …