Publications by Tamara G. Kolda

http://csmr.ca.sandia.gov/~tgkolda/ref#TensorReview
T. G. Kolda and B. W. Bader. Tensor Decompositions and Applications. SIAM Review, to appear (accepted June 2008). [PDF] [BibTeX] {older version}

Abstract: This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or N-way array. Decompositions of higher-order tensors (i.e., N-way arrays with N >= 3) have applications in psychometrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rankone tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.

Keywords: tensor decompositions, multiway arrays, multilinear algebra, parallel factors (PARAFAC), canonical decomposition (CANDECOMP), higher-order principal components analysis (Tucker), higher-order singular value decomposition (HOSVD)

http://csmr.ca.sandia.gov/~tgkolda/ref#ICDM08
T. G. Kolda and J. Sun. Scalable Tensor Decompositions for Multi-aspect Data Mining. In: ICDM 2008: Proceedings of the 8th IEEE International Conference on Data Mining, December 2008. [PDF] [BibTeX]

Abstract: Modern applications such as Internet traffic, telecommunication records, and large-scale social networks generate massive amounts of data with multiple aspects and high dimensionalities. Tensors (i.e., multi-way arrays) provide a natural representation for such data. Consequently, tensor decompositions such as Tucker become important tools for summarization and analysis. One major challenge is how to deal with highdimensional, sparse data. In other words, how do we compute decompositions of tensors where most of the entries of the tensor are zero. Specialized techniques are needed for computing the Tucker decompositions for sparse tensors because standard algorithms do not account for the sparsity of the data. As a result, a surprising phenomenon is observed by practitioners: Despite the fact that there is enough memory to store both the input tensors and the factorized output tensors, memory overflows occur during the tensor factorization process. To address this intermediate blowup problem, we propose Memory-Efficient Tucker (MET). Based on the available memory, MET adaptively selects the right execution strategy during the decomposition. We provide quantitative and qualitative evaluation of MET on real tensors. It achieves over 1000X space reduction without sacrificing speed; it also allows us to work with much larger tensors that were too big to handle before. Finally, we demonstrate a data mining case-study using MET.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2008-6553
J. D. Griffin and T. G. Kolda. Asynchronous parallel hybrid optimization combining DIRECT and GSS. Technical Report Number SAND2008-6553, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, October 2008. [PDF] [BibTeX]

Abstract: In this paper we explore hybrid parallel global optimization using DIRECT and asynchronous gener- ating set search (GSS). Both DIRECT and GSS are derivative-free and so require only objective function values; this makes these methods applicable to a wide variety of science and engineering problems. DI- RECT is a global search method that strategically divides the search space into ever-smaller rectangles, sampling the objective function at the center point for each rectangle. GSS is a (local) search method that samples the objective function at trial points around the current best point, i.e., the point with the lowest function value. Latin hypercube sampling (LHS) can be used to seed GSS with a good start- ing point. Using standard global optimization test problems, we compare the parallel performance of DIRECT and GSS with hybrids that combine the two methods. The hybrid methods are much faster than DIRECT and scale better when more processors are added. This improvement in performance is achieved without any sacrifice in the quality of the solution --- the hybrid methods and the global optimum whenever DIRECT does.

Keywords: parallel, asynchronous, distributed computing, hybrid optimization, global optimization, direct search, derivative-free, generating set search (GSS), pattern search

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2008-5844
N. Goldberg, T. G. Kolda and A. S. Yoshimura. Concurrent Optimization with DUET: DIRECT Using External Trial Points. Technical Report Number SAND2008-5844, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, September 2008. [PDF] [BibTeX]

Abstract: We consider the general problem of minimizing a real function subject to bound constraints. We are motivated by applications in which the derivatives of the objective function are unavailable or expensive to compute. This can occur, for example, when the function is not given analytically and is evaluated by running a simulation. The DIRECT algorithm by Jones, Pertunnen, and Stuckman is a global derivative-free op- timization algorithm. It is a deterministic algorithm that samples the space following a scheme that is justiable theoretically in case of Lipschitz continuous functions. In practice, DIRECT has proven to be ecient, with respect to the number of function evaluations, in nding a global minimum for a wide variety of functions. We extend the DIRECT algorithm to make use of additional free trial points that are made avail- able when running DIRECT simultaneously with other optimization algorithms. We compare several deterministic and randomized variants of the DIRECT algorithm that use the external trial points (DUET). We present experimental results with external trial points that are sampled at random to show an improvement of DUET over the performance of the DIRECT algorithm.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2008-6109
T. G. Kolda and B. W. Bader. Multi-way Data Analysis and Applications (extended abstract). In: Proceedings of the 2008 Sandia Workshop on Data Mining and Data Analysis, J. M. Brandt, D. M. Dunlavy and A. C. Gentile (eds.), Number SAND2008-6109, Pages 42-45, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, September 2008. [PDF] [BibTeX]

http://csmr.ca.sandia.gov/~tgkolda/ref#SIAM-66416
J. D. Griffin, T. G. Kolda and R. M. Lewis. Asynchronous Parallel Generating Set Search For Linearly-Constrained Optimization. SIAM Journal on Scientific Computing, Volume 30, Number 4, Pages 1892-1924, May 2008. (doi:10.1137/060664161) [PDF] [BibTeX] {older version}

Abstract: We describe an asynchronous parallel derivative-free algorithm for linearly constrained optimization. Generating set search (GSS) is the basis of our method. At each iteration, a GSS algorithm computes a set of search directions and corresponding trial points and then evaluates the objective function value at each trial point. Asynchronous versions of the algorithm have been developed in the unconstrained and bound-constrained cases which allow the iterations to continue (and new trial points to be generated and evaluated) as soon as any other trial point completes. This enables better utilization of parallel resources and a reduction in overall run time, especially for problems where the objective function takes minutes or hours to compute. For linearly constrained GSS, the convergence theory requires that the set of search directions conforms to the nearby boundary. This creates an immediate obstacle for asynchronous methods where the definition of nearby is not well defined. In this paper, we develop an asynchronous linearly constrained GSS method that overcomes this difficulty and maintains the original convergence theory. We describe our implementation in detail, including how to avoid function evaluations by caching function values and using approximate lookups. We test our implementation on every CUTEr test problem with general linear constraints and up to 1000 variables. Without tuning to individual problems, our implementation was able to solve 95% of the test problems with 10 or fewer variables, 73% of the problems with 11-100 variables, and nearly half of the problems with 100-1000 variables. To the best of our knowledge, these are the best results that have ever been achieved with a derivative-free method for linearly constrained optimization. Our asynchronous parallel implementation is freely available as part of the APPSPACK software.

Keywords: nonlinear programming; constrained optimization; linear constraints; direct search; derivative-free optimization; generalized pattern search; generating set search; asynchronous parallel optimization; asynchronous parallel pattern search

© 2008 Society for Industrial and Applied Mathematics

http://csmr.ca.sandia.gov/~tgkolda/ref#ShootoutPaper-AWR
K. R. Fowler, J. P. Reese, C. E. Kees, J. E. Dennis, Jr., C. T. Kelley, C. T. Miller, C. Audet, A. J. Booker, G. Couture, R. W. Darwin, M. W. Farthing, D. E. Finkel, J. M. Gablonsky, G. Gray and T. G. Kolda. A Comparison of Derivative-Free Optimization Methods for Groundwater Supply and Hydraulic Capture Community Problems. Advances in Water Resources, Volume 31, Number 5, Pages 743-757, May 2008. (doi:10.1016/j.advwatres.2008.01.010) [PDF] [BibTeX]

Abstract: Management decisions involving groundwater supply and remediation often rely on optimization techniques to determine an effective strategy. We introduce several derivative-free sampling methods for solving constrained optimization problems that have not yet been considered in this field, and we include a genetic algorithm for completeness. Two well-documented community problems are used for illustration purposes: a groundwater supply problem and a hydraulic capture problem. The community problems were found to be challenging applications due to the objective functions being nonsmooth, nonlinear, and having many local minima. Because the results were found to be sensitive to initial iterates for some methods, guidance is provided in selecting initial iterates for these problems that improve the likelihood of achieving significant reductions in the objective function to be minimized. In addition, we suggest some potentially fruitful areas for future research.

Keywords: Sampling methods, genetic algorithm, local minima, nondifferentiable objective function

http://csmr.ca.sandia.gov/~tgkolda/ref#SVDSIGN
R. Bro, E. Acar and T. G. Kolda. Resolving the sign ambiguity in the singular value decomposition. Journal of Chemometrics, Volume 22, Number 2, Pages 135-140, February 2008. (doi:10.1002/cem.1122) [BibTeX] {older version}

Abstract: Many modern data analysis methods involve computing a matrix singular value decomposition (SVD) or eigenvalue decomposition (EVD). Principal components analysis is the time-honored example, but more recent applications include latent semantic indexing, hypertext induced topic selection (HITS), clustering, classification, etc. Though the SVD and EVD are well-established and can be computed via state-of-the-art algorithms, it is not commonly mentioned that there is an intrinsic sign indeterminacy that can significantly impact the conclusions and interpretations drawn from their results. Here we provide a solution to the sign ambiguity problem and show how it leads to more sensible solutions.

Keywords: PCA, sign indeterminacy, SVD, sign flip

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2007-8018
B. W. Bader and T. G. Kolda. Final Report: Data Mining on Attributed Relationship Graphs. Technical Report Number SAND2007-8018, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, December 2007. [BibTeX]

http://csmr.ca.sandia.gov/~tgkolda/ref#SIAM-67648
B. W. Bader and T. G. Kolda. Efficient MATLAB computations with sparse and factored tensors. SIAM Journal on Scientific Computing, Volume 30, Number 1, Pages 205-231, December 2007. (doi:10.1137/060676489) [PDF] [BibTeX] {older version}

Abstract: In this paper, the term tensor refers simply to a multidimensional or N-way array, and we consider how specially structured tensors allow for efficient storage and computation. First, we study sparse tensors, which have the property that the vast majority of the elements are zero. We propose storing sparse tensors using coordinate format and describe the computational efficiency of this scheme for various mathematical operations, including those typical to tensor decomposition algorithms. Second, we study factored tensors, which have the property that they can be assembled from more basic components. We consider two specific types: A Tucker tensor can be expressed as the product of a core tensor (which itself may be dense, sparse, or factored) and a matrix along each mode, and a Kruskal tensor can be expressed as the sum of rank-1 tensors. We are interested in the case where the storage of the components is less than the storage of the full tensor, and we demonstrate that many elementary operations can be computed using only the components. All of the efficiencies described in this paper are implemented in the Tensor Toolbox for MATLAB.

Keywords: sparse multidimensional arrays; multilinear algebraic computations; tensor decompositions; Tucker model; parallel factors (PARAFAC) model; MATLAB classes; canonical decomposition (CANDECOMP)

© 2007 Society for Industrial and Applied Mathematics

http://csmr.ca.sandia.gov/~tgkolda/ref#SeleeStudentPaper2007
T. M. Selee, T. G. Kolda, W. P. Kegelmeyer and J. D. Griffin. Extracting Clusters from Large Datasets with Multiple Similarity Measures Using IMSCAND. In: CSRI Summer Proceedings 2007, Technical Report SAND2007-7977, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, M. L. Parks and S. S. Collis (eds.), Pages 87-103, December 2007. (http://www.cs.sandia.gov/CSRI/Proceedings/) [PDF] [BibTeX]

Abstract: We consider the problem of how to group information when multiple similarities are known. For a group of people, we may know their education, geographic location and family connections and want to cluster the people by treating all three of these similarities simultaneously. Our approach is to store each similarity as a slice in a tensor. The similarity measures are generated by comparing features. Generally, the object similarity matrix is dense. However it can be stored implicitly as the product of a sparse matrix, representing the object-feature matrix, and its transpose. For this new type of tensor where dense slices are stored implicitly, we have created a new decomposition called Implicit Slice Canonical Decomposition (IMSCAND). Our decomposition is equivalent to the tensor CANDECOMP/PARAFAC decomposition, which is a higher-order analogue of the matrix Singular Value decomposition (SVD) and Principal Component Analysis (PCA). From IMSCAND we obtain compilation feature vectors which are clustered using k-means. We demonstrate the applicability of IMSCAND on a set of journal articles with multiple similarities.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2007-6702
T. G. Kolda and B. W. Bader. Tensor Decompositions and Applications. Technical Report Number SAND2007-6702, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, November 2007. [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#ICDM07
B. W. Bader, R. A. Harshman and T. G. Kolda. Temporal Analysis of Semantic Graphs using ASALSAN. In: ICDM 2007: Proceedings of the 7th IEEE International Conference on Data Mining, Pages 33-42, October 2007. (doi:10.1109/ICDM.2007.54) [PDF] [BibTeX] {older version}

Abstract: ASALSAN is a new algorithm for computing three-way DEDICOM, which is a linear algebra model for analyzing intrinsically asymmetric relationships, such as trade among nations or the exchange of emails among individuals, that incorporates a third mode of the data, such as time. ASALSAN is unique because it enables computing the three-way DEDICOM model on large, sparse data. A nonnegative version of ASALSAN is described as well. When we apply these techniques to adjacency arrays arising from directed graphs with edges labeled by time, we obtain a smaller graph on latent semantic dimensions and gain additional information about their changing relationships over time. We demonstrate these techniques on international trade data and the Enron email corpus to uncover latent components and their transient behavior. The mixture of roles assigned to individuals by ASALSAN showed strong correspondence with known job classifications and revealed the patterns of communication between these roles. Changes in the communication pattern over time, e.g., between top executives and the legal department, were also apparent in the solutions.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2007-6422
R. Bro, E. Acar and T. G. Kolda. Resolving the sign ambiguity in the singular value decomposition. Technical Report Number SAND2007-6422, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, October 2007. [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#KDD2007
P. A. Chew, B. W. Bader, T. G. Kolda and A. Abdelali. Cross-language information retrieval using PARAFAC2. In: KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Pages 143-152, ACM Press, 2007. (doi:10.1145/1281192.1281211) [PDF] [BibTeX] {older version}

Abstract: (CLIR) uses Latent Semantic Analysis (LSA) in conjunction with a multilingual parallel aligned corpus. This approach has been shown to be successful in identifying similar documents across languages - or more precisely, retrieving the most similar document in one language to a query in another language. However, the approach has severe drawbacks when applied to a related task, that of clustering documents 'language independently', so that documents about similar topics end up closest to one another in the semantic space regardless of their language. The problem is that documents are generally more similar to other documents in the same language than they are to documents in a different language, but on the same topic. As a result, when using multilingual LSA, documents will in practice cluster by language, not by topic.

We propose a novel application of PARAFAC2 (which is a variant of PARAFAC, a multi-way generalization of the singular value decomposition [SVD]) to overcome this problem. Instead of forming a single multilingual term-by-document matrix which, under LSA, is subjected to SVD, we form an irregular three-way array, each slice of which is a separate term-by-document matrix for a single language in the parallel corpus. The goal is to compute an SVD for each language such that V (the matrix of right singular vectors) is the same across all languages. Effectively, PARAFAC2 imposes the constraint, not present in standard LSA, that the 'concepts' in all documents in the parallel corpus are the same regardless of language. Intuitively, this constraint makes sense, since the whole purpose of using a parallel corpus is that exactly the same concepts are expressed in the translations.

We tested this approach by comparing the performance of PARAFAC2 with standard LSA in solving a particular CLIR problem. From our results, we conclude that PARAFAC2 offers a very promising alternative to LSA not only for multilingual document clustering, but also for solving other problems in crosslanguage information retrieval.

Keywords: Latent Semantic Analysis (LSA), information retrieval, multilingual, clustering, PARAFAC2

http://csmr.ca.sandia.gov/~tgkolda/ref#SIGMOD2007-Tutorial
C. Faloutsos, T. G. Kolda and J. Sun. Mining large graphs and streams using matrix and tensor tools (extended abstract). In: SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data, Pages 1174-1174, ACM Press, 2007. (doi:10.1145/1247480.1247647) [PDF] [BibTeX]

Abstract: Coevolving streams of numerical measurements, as well astime evolving graphs, can well be represented as tensors. Here we review the fundamental matrix and tensors tools forthe analysis and mining of large scale streams and graphs.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2007-3257
J. D. Griffin and T. G. Kolda. Nonlinearly-constrained Optimization using Asynchronous Parallel Generating Set Search. Technical Report Number SAND2007-3257, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, May 2007. Submitted for publication. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2007/073257.pdf) [PDF] [BibTeX]

Abstract: Many optimization problems in computational science and engineering (CS&E) are characterized by expensive objective and/or constraint function evaluations paired with a lack of derivative information. Direct search methods such as generating set search (GSS) are well understood and efficient for derivative-free optimization of unconstrained and linearly-constrained problems. This paper addresses the more difficult problem of general nonlinear programming where derivatives for objective or constraint functions are unavailable, which is the case for many CS&E applications. We focus on penalty methods that use GSS to solve the linearly-constrained problems, comparing different penalty functions. A classical choice for penalizing constraint violations is l2^2, the squared l2 norm, which has advantages for derivative-based optimization methods. In our numerical tests, however, we show that exact penalty functions based on the l1, l2, and l-infintiy norms converge to good approximate solutions more quickly and thus are attractive alternatives. Unfortunately, exact penalty functions are discontinuous and consequently introduce theoretical problems that degrade the final solution accuracy, so we also consider smoothed variants. Smoothed-exact penalty functions are theoretically attractive because they retain the differentiability of the original problem. Numerically, they are a compromise between exact and l2^2, i.e., they converge to a good solution somewhat quickly without sacrificing much solution accuracy. Moreover, the smoothing is parameterized and can potentially be adjusted to balance the two considerations. Since many CS&E optimization problems are characterized by expensive function evaluations, reducing the number of function evaluations is paramount, and the results of this paper show that exact and smoothed-exact penalty functions are well-suited to this task.

Keywords: nonlinear programming, constrained optimization, penalty methods, direct search, derivative-free, generating set search (GSS), parallel, asynchronous

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2007-2706
P. A. Chew, B. W. Bader, T. G. Kolda and A. Abdelali. Cross-language information retrieval using PARAFAC2. Technical Report Number SAND2007-2706, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, May 2007. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2007/072706.pdf) [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-7744
B. W. Bader, R. Harshman and T. G. Kolda. Pattern Analysis of Directed Graphs Using DEDICOM: An Application to Enron Email. Technical Report Number SAND2006-7744, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, December 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/067744.pdf) [PDF] [BibTeX] {older version} {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-7592
B. W. Bader and T. G. Kolda. Efficient MATLAB computations with sparse and factored tensors. Technical Report Number SAND2006-7592, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, December 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/067592.pdf) [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#ACM-TOMS-TENSORTOOLBOX
B. W. Bader and T. G. Kolda. Algorithm 862: MATLAB tensor classes for fast algorithm prototyping. ACM Transactions on Mathematical Software, Volume 32, Number 4, Pages 635-653, December 2006. (doi:10.1145/1186785.1186794) [PDF] [BibTeX] {older version}

Abstract: Tensors (also known as multidimensional arrays or N-way arrays) are used in a variety of applications ranging from chemometrics to psychometrics. We describe four MATLAB classes for tensor manipulations that can be used for fast algorithm prototyping. The tensor class extends the functionality of MATLAB's multidimensional arrays by supporting additional operations such as tensor multiplication. The tensor_as_matrix class supports the "matricization" of a tensor, i.e., the conversion of a tensor to a matrix (and vice versa), a commonly used operation in many algorithms. Two additional classes represent tensors stored in decomposed formats: cp_tensor and tucker_tensor. We describe all of these classes and then demonstrate their use by showing how to implement several tensor algorithms that have appeared in the literature.

Keywords: Higher-Order Tensors, Multilinear Algebra, N-Way Arrays, MATLAB

http://csmr.ca.sandia.gov/~tgkolda/ref#SIAM-43363
T. G. Kolda, R. M. Lewis and V. Torczon. Stationarity results for generating set search for linearly constrained optimization. SIAM Journal on Optimization, Volume 17, Number 4, Pages 943-968, November 2006. (doi:10.1137/S1052623403433638) [PDF] [BibTeX] {older version}

Abstract: We present a new generating set search (GSS) approach for minimizing functions subject to linear constraints. GSS is a class of direct search optimization methods that includes generalized pattern search. One of our main contributions in this paper is a new condition to define the set of conforming search directions that admits several computational advantages. For continuously differentiable functions we also derive a bound relating a measure of stationarity, which is equivalent to the norm of the gradient of the objective in the unconstrained case, and a parameter used by GSS algorithms to control the lengths of the steps. With the additional assumption that the derivative is Lipschitz, we obtain a big-O bound. As a consequence of this relationship, we obtain subsequence convergence to a KKT point, even though GSS algorithms lack explicit gradient information. Numerical results indicate that the bound provides a reasonable estimate of stationarity.

Keywords: constrained optimization, linear constraints, global convergence analysis, direct search, generating set search, generalized pattern search, derivative-free methods, stopping criteria

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-4055
M. S. Eldred, A. A. Giunta, S. L. Brown, B. M. Adams, D. M. Dunlavy, J. P. Eddy, D. M. Gay, J. D. Griffin, W. E. Hart, P. D. Hough, T. G. Kolda, M. L. Martinez-Canales, L. P. Swiler, J. Watson and P. J. Williams. DAKOTA, a multilevel parallel object-oriented framework for design optimization, parameter estimation, uncertainty quantification, and sensitivity analysis: version 4.0 reference manual. Technical Report Number SAND2006-4055, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, October 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/064055.pdf) [PDF] [BibTeX]

Abstract: The DAKOTA (Design Analysis Kit for Optimization and Terascale Applications) toolkit provides a flexible and extensible interface between simulation codes and iterative analysis methods. DAKOTA contains algorithms for optimization with gradient and nongradientbased methods; uncertainty quantification with sampling, reliability, and stochastic finite element methods; parameter estimation with nonlinear least squares methods; and sensitivity/variance analysis with design of experiments and parameter study methods. These capabilities may be used on their own or as components within advanced strategies such as surrogate-based optimization, mixed integer nonlinear programming, or optimization under uncertainty. By employing object-oriented design to implement abstractions of the key components required for iterative systems analyses, the DAKOTA toolkit provides a flexible and extensible problem-solving environment for design and performance analysis of computational models on high performance computers.

This report serves as a reference manual for the commands specification for the DAKOTA software, providing input overviews, option descriptions, and example specifications.

http://csmr.ca.sandia.gov/~tgkolda/ref#ACM-TOMS-APPSPACK4
G. A. Gray and T. G. Kolda. Algorithm 856: APPSPACK 4.0: Asynchronous Parallel Pattern Search for Derivative-Free Optimization. ACM Transactions on Mathematical Software, Volume 32, Number 3, Pages 485-507, September 2006. (doi:10.1145/1163641.1163647) [PDF] [BibTeX] {older version}

Abstract: APPSPACK is software for solving unconstrained and bound constrained optimization problems. It implements an asynchronous parallel pattern search method that has been specifically designed for problems characterized by expensive function evaluations. Using APPSPACK to solve optimization problems has several advantages: No derivative information is needed; the procedure for evaluating the objective function can be executed via a separate program or script; the code can be run in serial or parallel, regardless of whether or not the function evaluation itself is parallel; and the software is freely available. We describe the underlying algorithm, data structures, and features of APPSPACK version 4.0 as well as how to use and customize the software.

Keywords: Parallel derivative-free optimization, pattern search

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-5315
T. G. Kolda, R. M. Lewis and V. Torczon. A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints. Technical Report Number SAND2006-5315, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, August 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/065315.pdf) [PDF] [BibTeX]

Abstract: We consider the solution of nonlinear programs in the case where derivatives of the objective function and nonlinear constraints are unavailable. To solve such problems, we propose an adaptation of a method due to Conn, Gould, Sartenaer, and Toint that proceeds by approximately minimizing a succession of linearly constrained augmented Lagrangians. Our modification is to use a derivative-free generating set direct search algorithm to solve the linearly constrained subproblems. The stopping criterion proposed by Conn, Gould, Sartenaer and Toint for the approximate solution of the subproblems requires explicit knowledge of derivatives. Such information is presumed absent in the generating set search method we employ. Instead, we show that stationarity results for linearly constrained generating set search methods provide a derivative-free stopping criterion, based on a step-length control parameter, that is sufficient to preserve the convergence properties of the original augmented Lagrangian algorithm.

Keywords: Nonlinear programming, augmented Lagrangian methods, constrained optimization, direct search, generating set search, generalized pattern search, derivative-free optimization

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-4621
J. D. Griffin, T. G. Kolda and R. M. Lewis. Asynchronous Parallel Generating Set Search For Linearly-Constrained Optimization. Technical Report Number SAND2006-4621, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, August 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/064621.pdf) [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#ICMS2006
J. D. Griffin and T. G. Kolda. A Parallel, Asynchronous Method for Derivative-Free Nonlinear Programs (extended abstract). In: Mathematical Software - ICMS 2006, Lecture Notes in Computer Science, Volume 4151, Pages 260-262, Springer, 2006. (doi:10.1007/11832225) [PDF] [BibTeX]

Abstract: Derivative-free optimization algorithms are needed to solve real-world engineering problems that have computationally expensive and noisy objective function and constraint evaluations. In particular, we are focused on problems that involve running cumbersome simulation codes with run times measured in hours. In such cases, attempts to compute derivatives can prove futile because analytical derivatives are typically unavailable and noise limits the accuracy of numerical approximations. Furthermore, the objective and constraint functions may be inherently nonsmooth, i.e., because the underlying model is nonsmooth.

© Springer-Verlag Berlin Heidelberg 2006

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-2161
B. W. Bader, R. Harshman and T. G. Kolda. Temporal analysis of social networks using three-way DEDICOM. Technical Report Number SAND2006-2161, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, April 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/062161.pdf) [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-2079
D. M. Dunlavy, T. G. Kolda and W. P. Kegelmeyer. Multilinear algebra for analyzing data with multiple linkages. Technical Report Number SAND2006-2079, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, April 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/062079.pdf) [PDF] [BibTeX]

Abstract: Link analysis typically focuses on a single type of connection, e.g., two journal papers are linked because they are written by the same author. However, often we want to analyze data that has multiple linkages between objects, e.g., two papers may have the same keywords and one may cite the other. The goal of this paper is to show that multilinear algebra provides a tool for multilink analysis. We analyze five years of publication data from journals published by the Society for Industrial and Applied Mathematics. We explore how papers can be grouped in the context of multiple link types using a tensor to represent all the links between them. A PARAFAC decomposition on the resulting tensor yields information similar to the SVD decomposition of a standard adjacency matrix. We show how the PARAFAC decomposition can be used to understand the structure of the document space and define paper-paper similarities based on multiple linkages. Examples are presented where the decomposed tensor data is used to find papers similar to a body of work (e.g., related by topic or similar to a particular author's papers), find related authors using linkages other than explicit co-authorship or citations, distinguish between papers written by different authors with the same name, and predict the journal in which a paper was published.

Keywords: PARAFAC, higher-order SVD, link analysis, citation analysis, document similarity

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2006-2081
T. G. Kolda. Multilinear operators for higher-order decompositions. Technical Report Number SAND2006-2081, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, April 2006. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2006/062081.pdf) [PDF] [BibTeX]

Abstract: We propose two new multilinear operators for expressing the matrix compositions that are needed in the Tucker and PARAFAC (CANDECOMP) decompositions. The first operator, which we call the Tucker operator, is shorthand for performing an n-mode matrix multiplication for every mode of a given tensor and can be employed to consisely express the Tucker decomposition. The second operator, which we call the Kruskal operator, is shorthand for the sum of the outer-products of the columns of N matrices and allows a divorce from a matricized representation and a very consise expression of the PARAFAC decomposition. We explore the properties of the Tucker and Kruskal operators independently of the related decompositions. Additionally, we provide a review of the matrix and tensor operations that are frequently used in the context of tensor decompositions.

Keywords: PARAFAC, CANDECOMP, Tucker, HOSVD, multilinear algebra, higher-order factor analysis, Khatri-Rao product

http://csmr.ca.sandia.gov/~tgkolda/ref#SDM06-LACS
T. Kolda and B. Bader. The TOPHITS model for higher-order web link analysis. In: Workshop on Link Analysis, Counterterrorism and Security, 2006. (http://www.cs.rit.edu/~amt/linkanalysis06/accepted/21.pdf) [PDF] [BibTeX]

Abstract: As the size of the web increases, it becomes more and more important to analyze link structure while also considering context. Multilinear algebra provides a novel tool for incorporating anchor text and other information into the authority computation used by link analysis methods such as HITS. Our recently proposed TOPHITS method uses a higher-order analogue of the matrix singular value decomposition called the PARAFAC model to analyze a three-way representation of web data. We compute hubs and authorities together with the terms that are used in the anchor text of the links between them. Adding a third dimension to the data greatly extends the applicability of HITS because the TOPHITS analysis can be performed in advance and offline. Like HITS, the TOPHITS model reveals latent groupings of pages, but TOPHITS also includes latent term information. In this paper, we describe a faster mathematical algorithm for computing the TOPHITS model on sparse data, and Web data is used to compare HITS and TOPHITS. We also discuss how the TOPHITS model can be used in queries, such as computing context-sensitive authorities and hubs. We describe different query response methodologies and present experimental results.

Keywords: PARAFAC, multilinear algebra, link analysis, higher-order SVD

http://csmr.ca.sandia.gov/~tgkolda/ref#SIAM-60358
T. G. Kolda. Revisiting asynchronous parallel pattern search for nonlinear optimization. SIAM Journal on Optimization, Volume 16, Number 2, Pages 563-586, December 2005. (doi:10.1137/040603589) [PDF] [BibTeX] {older version}

Abstract: We present a new asynchronous parallel pattern search (APPS) method which is different from that developed previously by Hough, Kolda, and Torczon. APPS efficiently uses parallel and distributed computing platforms to solve science and engineering design optimization problems where derivatives are unavailable and cannot be approximated. The original APPS was designed to be fault-tolerant as well as asynchronous and was based on a peer-to-peer design. Each process was in charge of a single, fixed search direction. Our new version is based instead on a manager-worker paradigm. Though less fault-tolerant, the resulting algorithm is more flexible in its use of distributed computing resources. We further describe how to incorporate a zero-order sufficient decrease condition and handle bound constraints. Convergence theory for all situations (unconstrained and bound constrained as well as simple and sufficient decrease) is developed. We close with a discussion of how the new APPS will better facilitate the future incorporation of linear and nonlinear constraints.

Keywords: asynchronous parallel optimization, pattern search, direct search, distributed computing, generating set search

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2005-6864
B. W. Bader, R. P. Pawlowski and T. G. Kolda. Robust large-scale parallel nonlinear solvers for simulations. Technical Report Number SAND2005-6864, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, November 2005. (http://www.prod.sandia.gov/cgi-bin/techlib/access-control.pl/2005/056864.pdf) [PDF] [BibTeX]

Abstract: This report documents research to develop robust and efficient solution techniques for solving large-scale systems of nonlinear equations. The most widely used method for solving systems of nonlinear equations is Newton's method. While much research has been devoted to augmenting Newton-based solvers (usually with globalization techniques), little has been devoted to exploring the application of different models. Our research has been directed at evaluating techniques using different models than Newton's method: a lower order model, Broyden's method, and a higher order model, the tensor method. We have developed large-scale versions of each of these models and have demonstrated their use in important applications at Sandia.

Broyden's method replaces the Jacobian with an approximation, allowing codes that cannot evaluate a Jacobian or have an inaccurate Jacobian to converge to a solution. Limited-memory methods, which have been successful in optimization, allow us to extend this approach to large-scale problems. We compare the robustness and efficiency of Newton's method, modified Newton's method, Jacobian-free Newton-Krylov method, and our limited-memory Broyden method. Comparisons are carried out for large-scale applications of fluid flow simulations and electronic circuit simulations. Results show that, in cases where the Jacobian was inaccurate or could not be computed, Broyden's method converged in some cases where Newton's method failed to converge. We identify conditions where Broyden's method can be more efficient than Newton's method.

We also present modifications to a large-scale tensor method, originally proposed by Bouaricha, for greater efficiency, better robustness, and wider applicability. Tensor methods are an alternative to Newton-based methods and are based on computing a step based on a local quadratic model rather than a linear model. The advantage of Bouaricha's method is that it can use any existing linear solver, which makes it simple to write and easily portable. However, the method usually takes twice as long to solve as Newton-GMRES on general problems because it solves two linear systems at each iteration. In this paper, we discuss modifications to Bouaricha's method for a practical implementation, including a special globalization technique and other modifications for greater efficiency. We present numerical results showing computational advantages over Newton-GMRES on some realistic problems.

We further discuss a new approach for dealing with singular (or ill-conditioned) matrices. In particular, we modify an algorithm for identifying a turning point so that an increasingly ill-conditioned Jacobian does not prevent convergence.

http://csmr.ca.sandia.gov/~tgkolda/ref#ICDM05
T. G. Kolda, B. W. Bader and J. P. Kenny. Higher-Order Web Link Analysis Using Multilinear Algebra. In: ICDM 2005: Proceedings of the 5th IEEE International Conference on Data Mining, Pages 242-249, November 2005. (doi:10.1109/ICDM.2005.77) [PDF] [BibTeX] {older version}

Abstract: Linear algebra is a powerful and proven tool in web search. Techniques, such as the PageRank algorithm of Brin and Page and the HITS algorithm of Kleinberg, score web pages based on the principal eigenvector (or singular vector) of a particular non-negative matrix that captures the hyperlink structure of the web graph. We propose and test a new methodology that uses multilinear algebra to elicit more information from a higher-order representation of the hyperlink graph. We start by labeling the edges in our graph with the anchor text of the hyperlinks so that the associated linear algebra representation is a sparse, three-way tensor. The first two dimensions of the tensor represent the web pages while the third dimension adds the anchor text. We then use the rank-1 factors of a multilinear PARAFAC tensor decomposition, which are akin to singular vectors of the SVD, to automatically identify topics in the collection along with the associated authoritative web pages.

http://csmr.ca.sandia.gov/~tgkolda/ref#ACM-TOMS-Trilinos-2005
M. A. Heroux, R. A. Bartlett, V. E. Howle, R. J. Hoekstra, J. J. Hu, T. G. Kolda, R. B. Lehoucq, K. R. Long, R. P. Pawlowski, E. T. Phipps, A. G. Salinger, H. K. Thornquist, R. S. Tuminaro, J. M. Willenbring, A. Williams and K. S. Stanley. An overview of the Trilinos project. ACM Transactions on Mathematical Software, Volume 31, Number 3, Pages 397-423, September 2005. (doi:10.1145/1089014.1089021) [PDF] [BibTeX] {older version}

Abstract: The Trilinos Project is an effort to facilitate the design, development, integration and ongoing support of mathematical software libraries within an object-oriented framework for the solution of large-scale, complex multi-physics engineering and scientific problems. Trilinos addresses two fundamental issues of developing software for these problems: (i) Providing a streamlined process and set of tools for development of new algorithmic implementations and (ii) promoting interoperability of independently developed software.

Trilinos uses a two-level software structure designed around collections of packages. A Trilinos package is an integral unit usually developed by a small team of experts in a particular algorithms area such as algebraic preconditioners, nonlinear solvers, etc. Packages exist underneath the Trilinos top level, which provides a common look-and-feel, including configuration, documentation, licensing, and bug-tracking.

Here we present the overall Trilinos design, describing our use of abstract interfaces and default concrete implementations. We discuss the services that Trilinos provides to a prospective package and how these services are used by various packages. We also illustrate how packages can be combined to rapidly develop new algorithms. Finally, we discuss how Trilinos facilitates highquality software engineering practices that are increasingly required from simulation software.

© 2005 ACM.

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2005-4548
T. G. Kolda, B. W. Bader and J. P. Kenny. Higher-Order Web Link Analysis Using Multilinear Algebra. Technical Report Number SAND2005-4548, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, July 2005. [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2005-6648
T. Kolda, D. Brown, J. Corones, T. Critchlow, T. Eliassi-Rad, L. Getoor, B. Hendrickson, V. Kumar, D. Lambert, C. Matarazzo, K. McCurley, M. Merrill, N. Samatova, D. Speck, R. Srikant, J. Thomas, M. Wertheimer and P. Wong. Data Sciences Technology for Homeland Security Information Management and Knowledge Discovery. Technical Report Number SAND2005-6648, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, January 2005. [PDF] [BibTeX]

Also released as Technical Report UCRL-TR-208926, Lawrence Livermore National Laboratory, Livermore, California, January 2005.

http://csmr.ca.sandia.gov/~tgkolda/ref#Complexities-2005
T. G. Kolda. An unexpected turn. In: Complexities: women in mathematics, B. A. Case and A. M. Leggett (eds.), Pages 388-390, Princeton University Press, January 2005. [BibTeX]

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2004-6391
G. A. Gray and T. G. Kolda. APPSPACK 4.0: asynchronous parallel pattern search for derivative-free optimization. Technical Report Number SAND2004-6391, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, December 2004. [PDF] [BibTeX] {newer version}

http://csmr.ca.sandia.gov/~tgkolda/ref#SAND2004-5187
B. W. Bader and T. G. Kolda. MATLAB tensor classes for fast algorithm prototyping. Technical Report Number SAND2004-5187, Sandia National Laboratories, Albuq