Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

New Insights from Aperiodic Variability of Young Stars

Nearly all young stars are variable, with the variability traditionally divided into two classes: periodic variables and aperiodic or "irregular" variables. Periodic variables have been studied extensively, typically using periodograms, while aperiodic variables have received much less attention due to a lack of standard statistical tools. However, aperiodic variability can serve as a powerful probe of young star accretion physics and inner circumstellar disk structure. For my dissertation, I analyzed data from a large-scale, long-term survey of the nearby North America Nebula complex, using Palomar Transient Factory photometric time series collected on a nightly or every few night cadence over several years. This survey is the most thorough exploration of variability in a sample of thousands of young stars over time baselines of days to years, revealing a rich array of lightcurve shapes, amplitudes, and timescales.

I have constrained the timescale distribution of all young variables, periodic and aperiodic, on timescales from less than a day to ~100 days. I have shown that the distribution of timescales for aperiodic variables peaks at a few days, with relatively few (~15%) sources dominated by variability on tens of days or longer. My constraints on aperiodic timescale distributions are based on two new tools, magnitude- vs. time-difference (Δm-Δt) plots and peak-finding plots, for describing aperiodic lightcurves; this thesis provides simulations of their performance and presents recommendations on how to apply them to aperiodic signals in other time series data sets. In addition, I have measured the error introduced into colors or SEDs from combining photometry of variable sources taken at different epochs. These are the first quantitative results to be presented on the distributions in amplitude and time scale for young aperiodic variables, particularly those varying on timescales of weeks to months.

Emprego da técnica de emissão por fluorescência de ultravioleta no monitoramento de inibidores de corrosão em água produzida

Para aumentar os volumes de extração de petróleo, resolver e prevenir problemas nas operações de produção são utilizados diversos produtos químicos, dentre os quais se destacam os inibidores de corrosão, que são utilizados em toda cadeia produtiva do petróleo visando proteger o sistema da deterioração por corrosão. Os sais de amônio quaternário são uma das classes de inibidores mais utilizadas pela indústria do petróleo devido a sua grande eficiência. Entretanto, sua solubilidade em água faz com que estejam presentes na água produzida representando um risco para contaminação ambiental, visto que possuem baixa biodegrabilidade e potencial de bioacumulação. Como se encontram misturados a outros produtos químicos e sob efeitos das variações do ambiente em que são aplicados, definir um método de análise confiável e viável para monitoramento em linha representa um desafio para os laboratórios de campos de produção. Neste trabalho, foi estudado o emprego da fluorescência de ultravioleta na quantificação de um inibidor de corrosão do tipo sal de amônio quaternário em água. Foram obtidos espectros de emissão do produto comercial em água, além do estudo de variáveis instrumentais e interferentes presentes na água produzida. A comparação com padrões de sal de amônio quaternário permitiu identificar como principal fluorófilo, um sal alquil-aril de amônio quaternário. Estudos de estabilidade revelaram que a adsorção do inibidor de corrosão nas superfícies dos frascos plásticos provoca a queda do sinal fluorescente e que a adição de isopropanol reduz este efeito de 40 para 24%. Foram obtidas curvas de calibração com a formulação comercial e com o cloreto de 2-metil-4-dodecil-benzil-trimetil amônio com uma boa correlação. Amostras sintéticas do inibidor foram determinadas com um erro relativo de 2,70 a 13,32%. O método de adição padrão foi avaliado usando uma amostra de água produzida, e os resultados não foram satisfatórios, devido à interferência, principalmente, de compostos orgânicos aromáticos presentes

Depth-sensitive analysis of fluorine on lunar sample surfaces and in carbonaceous chondrites by a nuclear resonant reaction technique

The nuclear resonant reaction ¹⁹F(ρ,αγ)¹⁶O has been used to perform depth-sensitive analyses of fluorine in lunar samples and carbonaceous chondrites. The resonance at 0.83 MeV (center-of-mass) in this reaction is utilized to study fluorine surface films, with particular interest paid to the outer micron of Apollo 15 green glass, Apollo 17 orange glass, and lunar vesicular basalts. These results are distinguished from terrestrial contamination, and are discussed in terms of a volcanic origin for the samples of interest. Measurements of fluorine in carbonaceous chondrites are used to better define the solar system fluorine abundance. A technique for measurement of carbon on solid surfaces with applications to direct quantitative analysis of implanted solar wind carbon in lunar samples is described.

Grants for Libraries

More and more libraries, museums and cultural institutions rely on fundraising and grant writing to sustain their services, special projects, or new initiatives Since most MLIS programs do not include grant project planning and proposal writing as part of their curriculum, librarians learn the process through trial and error, or continuing education classes. There are numerous books and websites that can assist the novice grant writer. We hope to provide beginners with basic information on the types of grants available, where to look for funding agencies, selected grant writing resources, and a few helpful grant writing hints to get you started. The presentation will be a three-person panel providing a short overview of the areas mentioned above, and discussion of sample grants submitted or received. The overview will be presented in Power Point format with an accompanying handout for each attendee.

Energy inequalities and error estimates for axisymmetric torsion of thin elastic shells of revolution

The problem motivating this investigation is that of pure axisymmetric torsion of an elastic shell of revolution. The analysis is carried out within the framework of the three-dimensional linear theory of elastic equilibrium for homogeneous, isotropic solids. The objective is the rigorous estimation of errors involved in the use of approximations based on thin shell theory.

The underlying boundary value problem is one of Neumann type for a second order elliptic operator. A systematic procedure for constructing pointwise estimates for the solution and its first derivatives is given for a general class of second-order elliptic boundary-value problems which includes the torsion problem as a special case.

The method used here rests on the construction of “energy inequalities” and on the subsequent deduction of pointwise estimates from the energy inequalities. This method removes certain drawbacks characteristic of pointwise estimates derived in some investigations of related areas.

Special interest is directed towards thin shells of constant thickness. The method enables us to estimate the error involved in a stress analysis in which the exact solution is replaced by an approximate one, and thus provides us with a means of assessing the quality of approximate solutions for axisymmetric torsion of thin shells.

Finally, the results of the present study are applied to the stress analysis of a circular cylindrical shell, and the quality of stress estimates derived here and those from a previous related publication are discussed.

Description of sampling stations, methods of benthic sampling and biological water quality assessment; with some consideration of the influence of sample variation on the assessment values obtained

The first bilateral study of methods of biological sampling and biological methods of water quality assessment took place during June 1977 on selected sampling sites in the catchment of the River Trent (UK). The study was arranged in accordance with the protocol established by the joint working group responsible for the Anglo-Soviet Environmental Agreement. The main purpose of the bilateral study in Nottingham was for some of the methods of sampling and biological assessment used by UK biologists to be demonstrated to their Soviet counterparts and for the Soviet biologists to have the opportunity to test these methods at first hand in order to judge the potential of any of these methods for use within the Soviet Union. This paper is concerned with the nine river stations in the Trent catchment.

Corroborative studies on the effects of sample variation on three macroinvertebrate biological assessment methods at different water quality states

In recent collaborative biological sampling exercises organised by the Nottingham Regional Laboratory of the Severn-Trent Water Authority, the effect of handnet sampling variation on the quality and usefulness of the data obtained has been questioned, especially when this data is transcribed into one or more of the commonly used biological methods of water quality assessment. This study investigates if this effect is constant at sites with similar typography but differing water quality states when the sampling method is standardized and carried out by a single operator. An argument is made for the use of a lowest common denominator approach to give a more consistent result and obviate the effect of sampling variation on these biological assessment methods.