<p> High performance linear algebra kernels are essential for scientific computing. Fast, accurate, and robust algorithms are required to process the large amount of data present in today's applications. In this thesis, we present new performance analysis, new error analysis, new stable algorithms, and new computational results. </p><p> An algorithm's performance depends on the computational cost and the communication cost. We begin with a study of the communication cost for dense linear algebra algorithms. We improve the lower bounds for the amount of communications in matrix multiplication. We also review optimal algorithms for dense linear algebra algorithms focusing on recursive algorithms. </p><p> We also consider the communication cost of the reduction operation. A reduction is a collective communication that is often used to communicate data in a parallel application. We present two new algorithms each developed under different models. In a unidirectional model, we prove our new algorithm is optimal. In a bidirectional model, we show experimentally our new algorithm has the same time complexity of a reverse optimal broadcast. Our implementations show that the new algorithms are viable options in practice. </p><p> In the remaining chapters, we turn our attention to error analysis. We present a complete error analysis study of computing an oblique QR factorization. As part of this study we introduce a new, stable, communication avoiding algorithm. Performance experiments confirm the benefit of the communication avoiding algorithms. </p><p> Finally, we consider the error due to the balancing algorithm, a preprocessing step to the nonsymmetric eigenvalue problem. We modify the balancing algorithm by improving its stopping criteria. We present several test cases where the previous balancing algorithm deteriorated the accuracy of the computation. The new algorithm successfully maintains satisfactory backward error for all test cases.</p>

No description available.

<p> In this thesis, we introduce and improve various methods for increasing the domains of convergence for iterative linear system solvers. We rely on the following three approaches: making the iteration adaptive, or nesting an inner iteration inside of a previously determined outer iteration; using deflation and projections to manipulate the spectra inherent to the iteration; and/or focusing on reordering schemes. We will analyze a specific combination of these three strategies. In particular, we propose to examine the influence of nesting a Flexible Generalized Minimum Residual algorithm together with an inner Recursive Projection Method using a banded preconditioner resulting from the Fiedler reordering.</p>

<p> We prove a combinatorial identity that relates the size of the value set of a map with the sizes of various iterated fiber products by this map. This identity is then used as the basis for several algorithms that calculate the size of the value set of a polynomial for a broad class of algebraic spaces, most generally an algorithm to calculate the size of the value set of a suitably well-behaved morphism between "nice" affine varieties defined over a finite field. In particular, these algorithms specialize to the case of calculating the size of the value set of a polynomial, viewed as a map between finite fields. These algorithms operate in deterministic polynomial time for fixed input polynomials (thus a fixed number of variables and polynomial degree), so long as the characteristic of the field grows suitably slowly as compared to the other parameters. </p><p> Each of these algorithms also produces a <i><b>fiber signature </b></i> for the map, which for each positive integer <i><b>j, </b></i> specifies how many points in the image have fibers of cardinality exactly <i><b>j.</b></i> </p><p> We adapt and analyze the zeta function calculation algorithms due to Lauder-Wan and Harvey, both as point counting algorithms and as algorithms for computation of one or many zeta functions. </p><p> These value set cardinality calculation algorithms extend to amortized cost algorithms that offer dramatic computational complexity advantages, when the computational cost is amortized over all the results produced. The last of these amortized algorithms partially answers a conjecture of Wan, as it operates in time that is polynomial in log <i><b>q</b></i> per value set cardinality calculated. </p><p> For the value set counting algorithms, these are the first such results, and offer a dramatic improvement over any previously known approach.</p>

Thesis (Ph.D.)--Indiana University, Dept. of Mathematics, 2007. / Source: Dissertation Abstracts International, Volume: 68-09, Section: B, page: 6011. Advisers: Jon M. Dunn; Lawrence S. Moss. Title from dissertation home page (viewed May 9, 2008).

Thesis (Ph.D.)--Indiana University, Dept. of Mathematics, 2007. / Source: Dissertation Abstracts International, Volume: 68-02, Section: B, page: 1015. Adviser: Lance J. Fortnow.

Thesis (Ph.D.)--Indiana University, Dept. of Mathematics, 2008. / Title from PDF t.p. (viewed on Jul 23, 2009). Source: Dissertation Abstracts International, Volume: 69-10, Section: B, page: 6139. Adviser: Jee Koh.

Thesis (Ph. D.)--University of Toronto, 2008. / Includes bibliographical references.

Thesis (Ph.D.)--Indiana University, Dept. of Mathematics, 2006. / "Title from dissertation home page (viewed July 11, 2007)." Source: Dissertation Abstracts International, Volume: 67-08, Section: B, page: 4466. Adviser: Daniel P. Maki.

<p>A common assumption in machine learning is that training and testing data are i.i.d. realizations of the same distribution. However, this assumption is often violated in practice: the training and test distributions are often somewhat related but different. For example, the training sample for a face recognition system may be a carefully curated data set in general different from the full face data found on online. Similarly, spam email messages change over time and thus the training sample for a spam classifier at any time differs from the test data. The first problem described above is known as domain adaptation and the second known as learning under drifting distributions. The first part of this thesis presents theory and algorithms for these problems. For domain adaptation, we provide tight learning bounds based on the novel concept of generalized discrepancy. These bounds strongly motivate our learning algorithm and it is shown, both theoretically and empirically, that this algorithm can significaly improve upon the current state-of-the-art. We extend the theoretical results of domain adaptation to the more challenging scenario of learning under drifting distributions. Moreover, we establish a deep connection between on-line learning and this problem. In particular, we provide a novel on-line to batch conversion that motivates a learning algorithm with very favorable empirical performance. The second part of this thesis studies a crucial problem at the intersection of learning and game theory: revenue optimization in repeated auctions. More precisely, we study second-price and generalized second-price auctions with reserve. These auction mechanisms have become extremely popular in recent years due to the advent of online advertisement. Both type of auctions are characterized by a reserve price representing the minimum value at which the seller is willing to forego of the object in question. Therefore, selecting an optimal reserve price is crucial in achieving the largest possible revenue. We cast this problem as a learning problem and provide the first theoretical analysis for learning optimal reserve prices from samples for both second-price and generalized second-price auctions. These results, however, assume that buyers do not react strategically to changes in reserve prices. In the last chapter of this thesis, we analyze the possible strategies for the buyers and show that, if the seller is more patient than the buyer, it is not in the best interest of the buyer to behave strategically.