Available Technical Reports
University of Maryland Computer Science Technical Reports

Listing of Univ. of Maryland CS technical reports by Dianne P. O'Leary

You are granted permission for the non-commercial reproduction, distribution, display, and performance of these technical reports in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).

Dianne P. O'Leary

Unpublished manuscript and varpro.m software
Variable Projection for Nonlinear Least Squares Problems, Dianne P. O'Leary and Bert W. Rust, 2011.

The variable projection algorithm of Golub and Pereyra (1973) has proven to be quite valuable in the solution of nonlinear least squares problems in which a substantial number of the parameters are linear. Its advantages are efficiency and, more importantly, a better likelihood of finding a global minimizer rather than a local one. The purpose of our work is to provide a more robust implementation of this algorithm, include constraints on the parameters, more clearly identify key ingredients so that improvements can be made, compute the Jacobian matrix more accurately, and make future implementations in other languages easy.

Modified Cholesky Algorithms: A Catalog with New Approaches, Haw-ren Fang and Dianne P. O'Leary, August 2006.

Given an $n \times n$ symmetric possibly indefinite matrix $A$, a modified Cholesky algorithm computes a factorization of the positive definite matrix $A+E$, where $E$ is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep $A+E$ well-conditioned and close to $A$. Gill, Murray and Wright introduced a stable algorithm, with a bound of $\|E\|_2=O(n^2)$. An algorithm of Schnabel and Eskow further guarantees $\|E\|_2=O(n)$. We present variants that also ensure $\|E\|_2=O(n)$. Mor\'{e} and Sorensen and Cheng and Higham used the block $LBL^T$ factorization with blocks of order $1$ or $2$. Algorithms in this class have a worst-case cost $O(n^3)$ higher than the standard Cholesky factorization, We present a new approach using an $LTL^T$ factorization, with $T$ tridiagonal, that guarantees a modification cost of at most $O(n^2)$.

QCS: A System for Querying, Clustering, and Summarizing Documents, Daniel M. Dunlavy, Dianne P. O'Leary, John M. Conroy, and Judith D. Schlesinger, July 2006.

Information retrieval systems consist of many complicated components. Research and development of such systems is often hampered by the difficulty in evaluating how each particular component would behave across multiple systems. We present a novel hybrid information retrieval system---the Query, Cluster, Summarize (QCS) system---which is portable, modular, and permits experimentation with different instantiations of each of the constituent text analysis components. Most importantly, the combination of the three types of components methods in the QCS design improves retrievals by providing users more focused information organized by topic. We demonstrate the improved performance by a series of experiments using standard test sets from the Document Understanding Conferences (DUC) along with the best known automatic metric for summarization system evaluation, {\tt ROUGE}. Although the DUC data and evaluations were originally designed to test multidocument summarization, we developed a framework to extend it to the task of evaluation for each of the three components: query, clustering, and summarization. Under this framework, we then demonstrate that the QCS system (end-to-end) achieves performance as good as or better than the best summarization engines. Given a query, QCS retrieves relevant documents, separates the retrieved documents into topic clusters, and creates a single summary for each cluster. In the current implementation, Latent Semantic Indexing is used for retrieval, generalized spherical k-means is used for the document clustering, and a method coupling sentence ``trimming,'' and a hidden Markov model, followed by a pivoted QR decomposition, is used to create a single extract summary for each cluster. The user interface is designed to provide access to detailed information in a compact and useful format. Our system demonstrates the feasibility of assembling an effective IR system from existing software libraries, the usefulness of the modularity of the design, and the value of this particular combination of modules.


Parallelism for Quantum Computation with Qudits Dianne P. O'Leary, Gavin K. Brennen, and Stephen S. Bullock,
Robust quantum computation with $d$-level quantum systems (qudits) poses two requirements: fast, parallel quantum gates and high fidelity two-qudit gates. We first describe how to implement parallel single qudit operations. It is by now well known that any single-qudit unitary can be decomposed into a sequence of Givens rotations on two-dimensional subspaces of the qudit state space. Using a coupling graph to represent physically allowed couplings between pairs of qudit states, we then show that the logical depth {(time)} of the parallel gate sequence is equal to the height of an associated tree. The implementation of a given unitary can then optimize the tradeoff between gate time and resources used. These ideas are illustrated for qudits encoded in the ground hyperfine states of the atomic alkalies $^{87}$Rb and $^{133}$Cs. Second, we provide a protocol for implementing parallelized non-local two-qudit gates using the assistance of entangled qubit pairs. {Using known protocols for qubit entanglement purification}, this offers the possibility of high fidelity two-qudit gates.


Homotopy Optimization Methods for Global Optimization, Daniel M. Dunlavy and Dianne P. O'Leary, December 2005.
We define a new method for global optimization, the Homotopy Optimization Method (HOM). This method differs from previous homotopy and continuation methods in that its aim is to find a minimizer for each of a set of values of the homotopy parameter, rather than to follow a path of minimizers. We define a second method, called HOPE, by allowing HOM to follow an ensemble of points obtained by perturbation of previous ones. We relate this new method to standard methods such as simulated annealing and show under what circumstances it is superior. We present results of extensive numerical experiments demonstrating performance of HOM and HOPE.


Efficient Circuits for Exact-Universal Computation with Qudits, Gavin K. Brennen, Stephen S. Bullock, and Dianne P. O'Leary, September 2005.
This paper concerns the efficient implementation of quantum circuits for qudits. We show that controlled two-qudit gates can be implemented without ancillas and prove that the gate library containing arbitrary local unitaries and one two-qudit gate, CINC, is exact-universal. A recent paper [S.Bullock, D.O'Leary, and G.K. Brennen, Phys. Rev. Let t. 94, 230502 (2005)] describes quantum circuits for qudits which require $O(d^n)$ two-qudit gates for state synthesis and $O(d^{2n})$ two-qudit gates for unitary synthesis, matching the respective lower bound complexities. In this work, we present the state synthesis circuit in much greater detail and prove that it is correct. Also, the $\lceil (n-2)/(d-2) \rceil$ ancillas required in the original algorithm may be removed without changing the asymptotics. Further, we present a new algorithm for unitary synthesis, inspired by the QR matrix decomposition, which is also asymptotically optimal.

Stable Factorizations of Symmetric Tridiagonal and Triadic Matrices Haw-ren Fang and Dianne P. O'Leary, July, 2005

We call a matrix triadic if it has no more than two nonzero off-diagonal elements in any column. A symmetric tridiagonal matrix is a special case. In this paper we consider $LXL^T$ factorizations of symmetric triadic matrices, where $L$ is unit lower triangular and $X$ is diagonal, block diagonal with 1x1 and 2x2 blocks, or the identity with $L$ lower triangular. We prove that with diagonal pivoting, the $LXL^T$ factorization of a symmetric triadic matrix is sparse, study some pivoting algorithms, discuss their growth factor and performance, analyze their stability, and develop perturbation bounds. These factorizations are useful in computing inertia, in solving linear systems of equations, and in determining modified Newton search directions.




CS-TR-4594 June 2004. updated version (April 2005)

CS-TR-4592 (updated)











Animated companion to the above two papers, Nagy and O'Leary, July 2000




Supplement to CS-TR-4012 April 1999, Kolda and O'Leary, SDDPACK software