Publications by Tamara G. Kolda


Abstract: Several tensor eigenpair definitions have been put forth in the past decade, but these can all be unified under generalized tensor eigenpair framework, introduced by Chang, Pearson, and Zhang [J. Math. Anal. Appl., 350 (2009), pp. 416--422]. Given mth-order, n-dimensional real-valued symmetric tensors $A$ and $B$, the goal is to find $lambda in R$ and $x in R^n, x neq 0$ such that $Ax^m-1 = lambda Bx^m-1$. Different choices for $B$ yield different versions of the tensor eigenvalue problem. We present our generalized eigenproblem adaptive power (GEAP) method for solving the problem, which is an extension of the shifted symmetric higher-order power method (SS-HOPM) for finding Z-eigenpairs. A major drawback of SS-HOPM is that its performance depended on choosing an appropriate shift, but our GEAP method also includes an adaptive method for choosing the shift automatically.

Keywords: tensor eigenvalues, E-eigenpairs, Z-eigenpairs, l2-eigenpairs, generalized tensor eigenpairs, shifted symmetric higher-order power method (SS-HOPM), generalized eigenproblem adaptive power (GEAP) method

BibTeX:
@article{KoMa14,  
author = {Tamara G. Kolda and Jackson R. Mayo}, 
title = {An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {35}, 
number = {4}, 
pages = {1563--1581}, 
month = {December}, 
year = {2014},
doi = {10.1137/140951758},	
url = {http://epubs.siam.org/toc/sjmael/35/4},
}

Abstract: Graphs and networks are used to model interactions in a variety of contexts. There is a growing need to quickly assess the characteristics of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle-based and give a measure of the connectedness of mutual friends. This is often summarized in terms of clustering coefficients, which measure the likelihood that two neighbors of a node are themselves connected. Computing these measures exactly for large-scale networks is prohibitively expensive in both memory and time. However, a recent wedge sampling algorithm has proved successful in efficiently and accurately estimating clustering coefficients. In this paper, we describe how to implement this approach in MapReduce to deal with extremely massive graphs. We show results on publicly-available networks, the largest of which is 132M nodes and 4.7B edges, as well as artificially generated networks (using the Graph500 benchmark), the largest of which has 240M nodes and 8.5B edges. We can estimate the clustering coefficient by degree bin (e.g., we use exponential binning) and the number of triangles per bin, as well as the global clustering coefficient and total number of triangles, in an average of 0.33 sec. per million edges plus overhead (approximately 225 sec. total for our configuration). The technique can also be used to study triangle statistics such as the ratio of the highest and lowest degree, and we highlight differences between social and non-social networks. To the best of our knowledge, these are the largest triangle-based graph computations published to date.

Keywords: triangle counting, clustering coefficient, triangle characteristics, large-scale networks, MapReduce

BibTeX:
@article{KoPiPlSeTa14,  
author = {Tamara G. Kolda and Ali Pinar and Todd Plantenga and C. Seshadhri and Christine Task}, 
title = {Counting Triangles in Massive Graphs with {MapReduce}}, 
journal = {SIAM Journal on Scientific Computing}, 
issuetitle = {Special Section on Two Themes: Planet Earth and Big Data}, 
volume = {36}, 
number = {5}, 
pages = {S44-S77},
pagetotal = {30} 
month = {October}, 
year = {2014},
doi = {10.1137/13090729X},
}

Abstract: We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued vectors. Algebraic methods exist for computing complex-valued decompositions of symmetric tensors, but here we focus on real-valued decompositions, both unconstrained and nonnegative. We discuss when solutions exist and how to formulate the mathematical program. Numerical results show the properties of the proposed formulations (including one that ignores symmetry) on a set of test problems and illustrate that these straightforward formulations can be effective even though the problem is nonconvex.

Keywords: symmetric, outer product, canonical polyadic, tensor decomposition, completely positive, nonnegative

BibTeX:
@misc{SymCP-arXiv-1410.4536,  
author = {Tamara G. Kolda}, 
title = {Numerical Optimization for Symmetric Tensor Decomposition}, 
month = {October}, 
year = {2014},
eprint = {1410.4536},
eprintclass = {math.NA},
}

Abstract: Symmetric tensor operations arise in a wide variety of computations. However, the benefits of exploiting symmetry in order to reduce storage and computation is in conflict with a desire to simplify memory access patterns. In this paper, we propose a blocked data structure (Blocked Compact Symmetric Storage) wherein we consider the tensor by blocks and store only the unique blocks of a symmetric tensor. We propose an algorithm-by-blocks, already shown of benefit for matrix computations, that exploits this storage format by utilizing a series of temporary tensors to avoid redundant computation. Further, partial symmetry within temporaries is exploited to further avoid redundant storage and redundant computation. A detailed analysis shows that, relative to storing and computing with tensors without taking advantage of symmetry and partial symmetry, storage requirements are reduced by a factor of O(m!) and computational requirements by a factor of O((m+1)!/2m), where m is the order of the tensor. However, as the analysis shows, care must be taken in choosing the correct block size to ensure these storage and computational benefits are achieved (particularly for low-order tensors). An implementation demonstrates that storage is greatly reduced and the complexity introduced by storing and computing with tensors by blocks is manageable. Preliminary results demonstrate that computational time is also reduced. The paper concludes with a discussion of how insights in this paper point to opportunities for generalizing recent advances in the domain of linear algebra libraries to the field of multi-linear computation.

BibTeX:
@article{ScLoVaKo14,  
author = {Martin D. Schatz and Tze-Meng Low and Robert A. {van de Geijn} and Tamara G. Kolda}, 
title = {Exploiting Symmetry in Tensors for High Performance}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {36}, 
number = {5}, 
pages = {C453--C479}, 
month = {September}, 
year = {2014},
doi = {10.1137/130907215},
}

Abstract: Network data is ubiquitous and growing, yet we lack realistic generative models that can be calibrated to match real-world data. The recently proposed Block Two-Level Erdos-Renyi (BTER) model can be tuned to capture two fundamental properties: degree distribution and clustering coefficients. The latter is particularly important for reproducing graphs with community structure, such as social networks. In this paper, we compare BTER to other scalable models and show that it gives a better fit to real data. We provide a scalable implementation that requires only O(d_max) storage where d_max is the maximum number of neighbors for a single node. The generator is trivially parallelizable, and we show results for a Hadoop implementation for a modeling a real-world web graph with over 4.6 billion edges. We propose that the BTER model can be used as a graph generator for benchmarking purposes and provide idealized degree distributions and clustering coefficient profiles that can be tuned for user specifications.

Keywords: graph generator, network data, block two-level Erdos-Renyi (BTER) model, large-scale graph benchmarks

BibTeX:
@article{KoPiPlSe14,  
author = {Tamara G. Kolda and Ali Pinar and Todd Plantenga and C. Seshadhri}, 
title = {A Scalable Generative Graph Model with Community Structure}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {36}, 
number = {5}, 
pages = {C424--C452}, 
month = {September}, 
year = {2014},
doi = {10.1137/130914218},
}

Abstract: Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of such graphs. Some of the most useful graph metrics are based on triangles, such as those measuring social cohesion. Despite the importance of these triadic measures, algorithms to compute them can be extremely expensive. We discuss the method of wedge sampling. This versatile technique allows for the fast and accurate approximation of various types of clustering coefficients and triangle counts. Furthermore, these techniques are extensible to counting directed triangles in digraphs. Our methods come with provable and practical time-approximation tradeoffs for all computations. We provide extensive results that show our methods are orders of magnitude faster than the state of the art, while providing nearly the accuracy of full enumeration.

BibTeX:
@article{SePiKo14,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs}, 
journal = {Statistical Analysis and Data Mining}, 
volume = {7}, 
number = {4}, 
pages = {294-307}, 
month = {August}, 
year = {2014},
doi = {10.1002/sam.11224},
eprint = {1309.3321},
}

Abstract: In a graph, a community may be loosely defined as a group of nodes that are more closely connected to one another than to the rest of the graph. While there are a variety of metrics that can be used to specify the quality of a given community, one common theme is that flows tend to stay within communities. Hence, we expect cycles to play an important role in community detection. For undirected graphs, the importance of triangles --- an undirected 3-cycle --- has been known for a long time and can be used to improve community detection. In directed graphs, the situation is more nuanced. The smallest cycle is simply two nodes with a reciprocal connection, and using information about reciprocation has proven to improve community detection. Our new idea is based on the four types of directed triangles that contain cycles. To identify communities in directed networks, then, we propose an undirected edge-weighting scheme based on the type of the directed triangles in which edges are involved. We also propose a new metric on quality of the communities that is based on the number of 3-cycles that are split across communities. To demonstrate the impact of our new weighting, we use the standard METIS graph partitioning tool to determine communities and show experimentally that the resulting communities result in fewer 3-cycles being cut. The magnitude of the effect varies between a 10 and 50% reduction, and we also find evidence that this weighting scheme improves a task where plausible ground-truth communities are known.

Keywords: community detection, directed networks, triangles, reciprocity, 3-cycles

BibTeX:
@inproceedings{KlGlKo14,  
author = {Christine Klymko and David F. Gleich and Tamara G. Kolda}, 
title = {Using Triangles to Improve Community Detection in Directed Networks}, 
booktitle = {The Second ASE International Conference on Big Data Science and Computing, BigDataScience},
venue = {Stanford, CA},
eventdate = {2014-05-27/2014-05-31}, 
year = {2014},	
url = {http://www.ase360.org/handle/123456789/104},
}

BibTeX:
@misc{arXiv-1404.5874,  
author = {Christine Klymko and David Gleich and Tamara G. Kolda}, 
title = {Using Triangles to Improve Community Detection in Directed Networks}, 
month = {April}, 
year = {2014},
eprint = {1404.5874},
}

Abstract: Community detection is extremely expensive, and the cost generally depends at least linearly on the number of vertices in the graph. We propose working with a reduced graph that has many fewer nodes but nonetheless captures key community structure. The K-core of a graph is the largest subgraph within which each node has at least K connections. We propose a framework that accelerates community detection by applying an expensive algorithm (modularity optimization, the Louvain method, spectral clustering, etc.) to the K-core and then using an inexpensive heuristic (such as local modularity maximization) to infer community labels for the remaining nodes. Our experiments demonstrate that the proposed framework can reduce the running time by more than 80% while preserving the quality of the solutions. Recent theoretical investigations provide support for using the K-core as a reduced representation.

Keywords: K-core, Community Detection, Modularity

Revised October 2014.

BibTeX:
@misc{kcore-arXiv-1403.2226,  
author = {Chengbin Peng and Tamara G. Kolda and Ali Pinar}, 
title = {Accelerating Community Detection by Using {K-core} Subgraphs}, 
month = {March}, 
year = {2014},
eprint = {1403.2226},
}

BibTeX:
@misc{GTEP-arXiv-1401.1183,  
author = {Tamara G. Kolda and Jackson R. Mayo}, 
title = {An Adaptive Shifted Power Method for Computing Generalized Tensor Eigenpairs}, 
month = {January}, 
year = {2014},
eprint = {1401.1183},
}

BibTeX:
@misc{Wedges-arXiv:1309.3321,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs}, 
month = {September}, 
year = {2013},
eprint = {1309.3321},
}

Abstract: Understanding the dynamics of reciprocation is of great interest in sociology and computational social science. The recent growth of Massively Multi-player Online Games (MMOGs) has provided unprecedented access to large-scale data which enables us to study such complex human behavior in a more systematic manner. In this paper, we consider three different networks in the EverQuest2 game: chat, trade, and trust. The chat network has the highest level of reciprocation (33 because there are essentially no barriers to it. The trade network has a lower rate of reciprocation (27 because it has the obvious barrier of requiring goods or money for exchange; morever, there is no clear benefit to returning a trade link except in terms of social connections. The trust network has the lowest reciprocation (14 because this equates to sharing certain within-game assets such as weapons, and so there is a high barrier for such connections In general, we observe that reciprocation rate is inversely related to the barrier level in these networks. We also note that reciprocation has connections across the heterogeneous networks. Our experiments indicate that players make use of the medium-barrier reciprocations to strengthen a relationship. We hypothesize that lower-barrier interactions are an important component to predicting higher-barrier ones. We verify our hypothesis using predictive models for trust reciprocations with features from trade interactions. Incorporating the number of trades (both before and after the initial trust link) boosts our ability to predict if the trust will be reciprocated up to 11% with respect to the AUC. More generally, we see strong correlations across the different networks and emphasize that network dynamics, such as reciprocation, cannot be studied in isolation on just a single type of connection.

Keywords: MMOGs, multi-relational network, prediction, reciprocation, trust

ASONAM13 acceptance rate is 28% overall.

BibTeX:
@inproceedings{SiSuSrKo13,  
author = {Singhal, Ayush and Subbian, Karthik and Srivastava, Jaideep and Kolda, Tamara G. and Pinar, Ali}, 
title = {Dynamics of Trust Reciprocation in Multi-relational Networks}, 
booktitle = {ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining},
venue = {Niagara Falls, Canada},
eventdate = {2013-08-25/2013-08-28}, 
publisher = {ACM}, 
pages = {661--665}, 
year = {2013},
doi = {10.1145/2492517.2555242},
}

BibTeX:
@article{SIAMNEWS-CSE13,  
author = {Tamara G. Kolda and Ali Pinar}, 
title = {Large-scale Network Analysis at SIAM CSE Conference}, 
journal = {SIAM News}, 
volume = {46}, 
number = {5}, 
month = {June}, 
year = {2013},	
url = {http://www.siam.org/news/news.php?id=2079},
urldate = {2014-04-03},
}

Abstract: Graphs are used to model interactions in a variety of contexts, and there is a growing need to quickly assess the structure of a graph. Some of the most useful graph metrics, especially those measuring social cohesion, are based on triangles. Despite the importance of these triadic measures, associated algorithms can be extremely expensive. We discuss the method of wedge sampling. This versatile technique allows for the fast and accurate approximation of all current variants of clustering coefficients and enables rapid uniform sampling of the triangles of a graph. Our methods come with provable and practical time-approximation tradeoffs for all computations. We provide extensive results that show our methods are orders of magnitude faster than the state-of-the-art, while providing nearly the accuracy of full enumeration. Our results will enable more wide-scale adoption of triadic measures for analysis of extremely large graphs, as demonstrated on several real-world examples.

Keywords: triangle counting, directed triangle counting, clustering coefficient, Hoeffding's inequality

Winner of SDM13 Best Paper Prize!

BibTeX:
@inproceedings{SePiKo13a,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {Triadic Measures on Graphs: The Power of Wedge Sampling}, 
booktitle = {SDM13: Proceedings of the 2013 SIAM International Conference on Data Mining},
venue = {Austin, TX},
eventdate = {2013-05-02/2013-05-04}, 
pages = {10--18}, 
year = {2013},
doi = {10.1137/1.9781611972832.2},
}

Abstract: Degree distributions are arguably the most important property of real world networks. The classic edge configuration model or Chung-Lu model can generate an undirected graph with any desired degree distribution. This serves as a good null model to compare algorithms or perform experimental studies. Furthermore, there are scalable algorithms that implement these models and they are invaluable in the study of graphs. However, networks in the real-world are often directed, and have a significant proportion of reciprocal edges. A stronger relation exists between two nodes when they each point to one another (reciprocal edge) as compared to when only one points to the other (one-way edge). Despite their importance, reciprocal edges have been disregarded by most directed graph models. We propose a null model for directed graphs inspired by the Chung-Lu model that matches the in-, out-, and reciprocal-degree distributions of the real graphs. Our algorithm is scalable and requires O(m) random numbers to generate a graph with m edges. We perform a series of experiments on real datasets and compare with existing graph models.

BibTeX:
@inproceedings{DuKoPiSe13,  
author = {Nurcan Durak and Tamara G. Kolda and Ali Pinar and C. Seshadhri}, 
title = {A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal}, 
booktitle = {NSW 2013: Proceedings of IEEE 2013 2nd International Network Science Workshop},
venue = {West Point, NY},
eventdate = {2013-04-29/2013-05-01}, 
pages = {23--30}, 
month = {April}, 
year = {2013},
doi = {10.1109/NSW.2013.6609190},
}

Abstract: Tensor factorizations with nonnegative constraints have proved to be powerful tools for analysis of sparse count data in areas such as bioinformatics and social network analysis. We consider application data best described as being generated by a Poisson process (e.g., count data), which leads to sparse tensors that are typically modeled by sparse factor matrices. In this paper we investigate efficient techniques for computing an appropriate tensor factorization model and propose new subproblem solvers within the standard alternating block variable approach. Our new methods exploit structure and reformulate the optimization problem as small independent subproblems. We employ bound-constrained Newton and quasi-Newton methods. We compare our algorithms against other codes, demonstrating superior speed for high accuracy results and the ability to quickly find sparse solutions.

Submitted for publication. Revised December 2013, July 2014.

BibTeX:
@misc{PTF-arXiv-1304.4964,  
author = {Samantha Hansen and Todd Plantenga and Tamara G. Kolda}, 
title = {Newton-Based Optimization for Nonnegative Tensor Factorizations}, 
month = {April}, 
year = {2013},
eprint = {1304.4964},
eprintclass = {math.NA},
}

Abstract: Graph analysis is playing an increasingly important role in science and industry. Due to numerous limitations in sharing real-world graphs, models for generating massive graphs are critical for developing better algorithms. In this article, we analyze the stochastic Kronecker graph model (SKG), which is the foundation of the Graph500 supercomputer benchmark due to its favorable properties and easy parallelization. Our goal is to provide a deeper understanding of the parameters and properties of this model so that its functionality as a benchmark is increased. We develop a rigorous mathematical analysis that shows this model cannot generate a power-law distribution or even a lognormal distribution. However, we formalize an enhanced version of the SKG model that uses random noise for smoothing. We prove both in theory and in practice that this enhancement leads to a lognormal distribution. Additionally, we provide a precise analysis of isolated vertices, showing that the graphs that are produced by SKG might be quite different than intended. For example, between 50% and 75% of the vertices in the Graph500 benchmarks will be isolated. Finally, we show that this model tends to produce extremely small core numbers (compared to most social networks and other real graphs) for common parameter choices.

Keywords: graph models, R-MAT, Stochastic Kronecker Graphs (SKG), Graph500

BibTeX:
@article{SePiKo13,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {An In-Depth Analysis of Stochastic {Kronecker} Graphs}, 
journal = {Journal of the ACM}, 
volume = {60}, 
number = {2},
eid = {13},
pagetotal = {32} 
month = {April}, 
year = {2013},
doi = {10.1145/2450142.2450149},
}

BibTeX:
@misc{MMOG-arXiv-1303.6385,  
author = {Karthik Subbian and Ayush Singhal and Tamara G. Kolda and Ali Pinar and Jaideep Srivastava}, 
title = {Dynamics of Trust Reciprocation in Heterogeneous {MMOG} Networks}, 
month = {March}, 
year = {2013},
eprint = {1303.6385},
eprintclass = {cs.SI},
}

BibTeX:
@misc{BTER-arXiv-1302.6636,  
author = {Tamara G. Kolda and Ali Pinar and Todd Plantenga and C. Seshadhri}, 
title = {A Scalable Generative Graph Model with Community Structure}, 
month = {February}, 
year = {2013},
eprint = {1302.6636},
eprintclass = {cs.SI},
}

Abstract: The study of triangles in graphs is a standard tool in network analysis. Real-world networks are often directed and have a significant fraction of reciprocal edges. Direction leads to many complexities, and it can be difficult to "measure" this structure meaningfully. We propose a collection of directed closure values that are analogues of the classic transitivity measure (the fraction of wedges that participate in triangles). Our study of these values reveals a wealth of information of the nature of direction. For instance, we immediately see the importance of reciprocal edges in forming triangles and can measure the power of transitivity. Surprisingly, the chance that a wedge is closed depends heavily on its directed structure. We also observe striking similarities between the triadic closure patterns of different web and social networks.

Keywords: wedge closure, transitivity, directed triangles, sampling

BibTeX:
@misc{DirectedTriangles-arXiv-1302.6220,  
author = {C. Seshadhri and Ali Pinar and Nurcan Durak and Tamara G. Kolda}, 
title = {Directed Closure Measures for Networks with Reciprocity}, 
month = {February}, 
year = {2013},
eprint = {1302.6220},
eprintclass = {cs.SI},
}

BibTeX:
@misc{SymTen-arXiv-1301.7744,  
author = {Martin D. Schatz and Tze Meng Low and Robert A. {van de Geijn} and Tamara G. Kolda}, 
title = {Exploiting Symmetry in Tensors for High Performance}, 
month = {January}, 
year = {2013},
eprint = {1301.7744},
eprintclass = {math.NA},
}

BibTeX:
@misc{TriMR-arXiv-1301.5887,  
author = {Tamara G. Kolda and Ali Pinar and Todd Plantenga and C. Seshadhri and Christine Task}, 
title = {Counting Triangles in Massive Graphs with {MapReduce}}, 
month = {January}, 
year = {2013},
eprint = {1301.5887},
eprintclass = {cs.SI},
}

Abstract: Tensors have found application in a variety of fields, ranging from chemometrics to signal processing and beyond. In this paper, we consider the problem of multilinear modeling of sparse count data. Our goal is to develop a descriptive tensor factorization model of such data, along with appropriate algorithms and theory. To do so, we propose that the random variation is best described via a Poisson distribution, which better describes the zeros observed in the data as compared to the typical assumption of a Gaussian distribution. Under a Poisson assumption, we fit a model to observed data using the negative log-likelihood score. We present a new algorithm for Poisson tensor factorization called CANDECOMP-PARAFAC alternating Poisson regression (CP-APR) that is based on a majorization-minimization approach. It can be shown that CP-APR is a generalization of the Lee-Seung multiplicative updates. We show how to prevent the algorithm from converging to non-KKT points and prove convergence of CP-APR under mild conditions. We also explain how to implement CP-APR for large-scale sparse tensors and present results on several data sets, both real and simulated.

Keywords: nonnegative tensor factorization, nonnegative CANDECOMP-PARAFAC, Poisson tensor factorization, Lee-Seung multiplicative updates, majorization-minimization algorithms

BibTeX:
@article{ChKo12,  
author = {Eric C. Chi and Tamara G. Kolda}, 
title = {On Tensors, Sparsity, and Nonnegative Factorizations}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {33}, 
number = {4}, 
pages = {1272-1299}, 
month = {December}, 
year = {2012},
doi = {10.1137/110859063},
}

Abstract: Triangles are an important building block and distinguishing feature of real-world networks, but their structure is still poorly understood. Despite numerous reports on the abundance of triangles, there is very little information on what these triangles look like. We initiate the study of degree-labeled triangles, - specifically, degree homogeneity versus heterogeneity in triangles. This yields new insight into the structure of real-world graphs. We observe that networks coming from social and collaborative situations are dominated by homogeneous triangles, i.e., degrees of vertices in a triangle are quite similar to each other. On the other hand, information networks (e.g., web graphs) are dominated by heterogeneous triangles, i.e., the degrees in triangles are quite disparate. Surprisingly, nodes within the top 1% of degrees participate in the vast majority of triangles in heterogeneous graphs. We investigate whether current graph models reproduce the types of triangles that are observed in real data and observe that most models fail to accurately capture these salient features

Keywords: graph models, social networks, triangles in graphs

Short paper: 28% acceptance rate.

BibTeX:
@inproceedings{DuPiKoSe12,  
author = {Durak, Nurcan and Pinar, Ali and Kolda, Tamara G. and Seshadhri, C.}, 
title = {Degree Relations of Triangles in Real-world Networks and Graph Models}, 
booktitle = {CIKM'12: Proceedings of the 21st ACM International Conference on Information and Knowledge Management},
venue = {Maui, Hawaii},
eventdate = {2012-10-29/2012-11-02}, 
publisher = {ACM}, 
pages = {1712--1716}, 
year = {2012},
doi = {10.1145/2396761.2398503},
}

BibTeX:
@misc{FRD-arXiv-1210.5288,  
author = {Nurcan Durak and Tamara G. Kolda and Ali Pinar and C. Seshadhri}, 
title = {A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal}, 
month = {October}, 
year = {2012},
eprint = {1210.5288},
eprintclass = {cs.SI},
}

BibTeX:
@misc{TriProp-arXiv_1207.7125,  
author = {Nurcan Durak and Ali Pinar and Tamara G. Kolda and C. Seshadhri}, 
title = {Degree Relations of Triangles in Real-world Networks and Models}, 
month = {July}, 
year = {2012},
eprint = {1207.7125},
eprintclass = {cs.SI},
}

Abstract: Community structure plays a significant role in the analysis of social networks and similar graphs, yet this structure is little understood and not well captured by most models. We formally define a community to be a subgraph that is internally highly connected and has no deeper substructure. We use tools of combinatorics to show that any such community must contain a dense Erdős-Rényi (ER) subgraph. Based on mathematical arguments, we hypothesize that any graph with a heavy-tailed degree distribution and community structure must contain a scale free collection of dense ER subgraphs. These theoretical observations corroborate well with empirical evidence. From this, we propose the Block Two-Level Erdős-Rényi (BTER) model, and demonstrate that it accurately captures the observable properties of many real-world social networks.

Source code available at http://www.sandia.gov/~tgkolda/bter_supplement/.

BibTeX:
@article{SeKoPi12,  
author = {C. Seshadhri and Tamara G. Kolda and Ali Pinar}, 
title = {Community Structure and Scale-free Collections of {Erd\H{o}s-R\'enyi} Graphs}, 
journal = {Physical Review~E}, 
volume = {85}, 
number = {5},
eid = {056109},
pagetotal = {9} 
month = {May}, 
year = {2012},
doi = {10.1103/PhysRevE.85.056109},
}

Abstract: The analysis of massive graphs is now becoming a very important part of science and industrial research. This has led to the construction of a large variety of graph models, each with their own advantages. The Stochastic Kronecker Graph (SKG) model has been chosen by the Graph500 steering committee to create supercomputer benchmarks for graph algorithms. The major reasons for this are its easy parallelization and ability to mirror real data. Although SKG is easy to implement, there is little understanding of the properties and behavior of this model. We show that the parallel variant of the edge-configuration model given by Chung and Lu (referred to as CL) is notably similar to the SKG model. The graph properties of an SKG are extremely close to those of a CLgraph generated with the appropriate parameters. Indeed, the final probability matrix used by SKG is almost identical to that of a CL model. This implies that the graph distribution represented by SKG is almost the same as that given by a CL model. We also show that when it comes to fitting real data, CL performs as well as SKG based on empirical studies of graph properties. CL has the added benefit of a trivially simple fitting procedure and exactly matching the degree distribution. Our results suggest that users of the SKG model should consider the CL model because of its similar properties, simpler structure, and ability to fit a wider range of degree distributions. At the very least, CL is a good control model to compare against.

BibTeX:
@inproceedings{PiSeKo12,  
author = {Ali Pinar and C. Seshadhri and Tamara G. Kolda}, 
title = {The Similarity between Stochastic {Kronecker} and {Chung-Lu} Graph Models}, 
booktitle = {SDM12: Proceedings of the 12th SIAM International Conference on Data Mining},
venue = {Anaheim, CA},
eventdate = {2012-04-26/2012-04-28}, 
pages = {1071-1082}, 
year = {2012},
doi = {10.1137/1.9781611972825.92},
}

BibTeX:
@misc{Triangles-arXiv-1202.5230,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {Triadic Measures on Graphs: The Power of Wedge Sampling}, 
month = {February}, 
year = {2012},
eprint = {1202.5230},
eprintclass = {cs.SI},
}

BibTeX:
@misc{BTER-arXiv-1112.3644,  
author = {C. Seshadhri and Tamara G. Kolda and Ali Pinar}, 
title = {Community Structure and Scale-free Collections of {Erd\H{o}s-R\'enyi} Graphs}, 
month = {December}, 
year = {2011},
eprint = {1112.3644},
eprintclass = {cs.SI},
}

BibTeX:
@misc{PTF-arXiv-1112.2414,  
author = {Eric C. Chi and Tamara G. Kolda}, 
title = {On Tensors, Sparsity, and Nonnegative Factorizations}, 
month = {December}, 
year = {2011},
eprint = {1112.2414},
eprintclass = {math.NA},
}

Abstract: COMET is a single-pass MapReduce algorithm for learning on large-scale data. It builds multiple random forest ensembles on distributed blocks of data and merges them into a mega-ensemble. This approach is appropriate when learning from massive-scale data that is too large to fit on a single machine. To get the best accuracy, IVoting should be used instead of bagging to generate the training subset for each decision tree in the random forest. Experiments with two large datasets (5GB and 50GB compressed) show that COMET compares favorably (in both accuracy and training time) to learning on a subsample of data using a serial algorithm. Finally, we propose a new Gaussian approach for lazy ensemble evaluation which dynamically decides how many ensemble members to evaluate per data point; this can reduce evaluation cost by 100X or more.

Full paper: 18% acceptance rate.

BibTeX:
@inproceedings{BaMuKoDi11,  
author = {Justin D. Basilico and M. Arthur Munson and Tamara G. Kolda and Kevin R. Dixon and W. Philip Kegelmeyer}, 
title = {{COMET}: A Recipe for Learning and Using Large Ensembles on Massive Data}, 
booktitle = {ICDM 2011: Proceedings of the 2011 IEEE International Conference on Data Mining},
venue = {Vancouver, BC},
eventdate = {2011-12-11/2011-12-14}, 
pages = {41--50}, 
year = {2011},
doi = {10.1109/ICDM.2011.39},
}

Full paper: 18% acceptance rate.

BibTeX:
@inproceedings{SePiKo11,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {An In-Depth Study of Stochastic {Kronecker} Graphs}, 
booktitle = {ICDM 2011: Proceedings of the 2011 IEEE International Conference on Data Mining},
venue = {Vancouver, BC},
eventdate = {2011-12-11/2011-12-14}, 
pages = {587--596}, 
year = {2011},
doi = {10.1109/ICDM.2011.23},
}

BibTeX:
@misc{SKG-CL-arXiv-1110.4925,  
author = {Ali Pinar and C. Seshadhri and Tamara G. Kolda}, 
title = {The Similarity between Stochastic {Kronecker} and {Chung-Lu} Graph Models}, 
month = {October}, 
year = {2011},
eprint = {1110.4925},
eprintclass = {cs.SI},
}

Abstract: Recent work on eigenvalues and eigenvectors for tensors of order m >= 3 has been motivated by applications in blind source separation, magnetic resonance imaging, molecular conformation, and more. In this paper, we consider methods for computing real symmetric-tensor eigenpairs of the form Ax^m-1 = lambda x subject to x=1, which is closely related to optimal rank-1 approximation of a symmetric tensor. Our contribution is a shifted symmetric higher-order power method (SS-HOPM), which we show is guaranteed to converge to a tensor eigenpair. SS-HOPM can be viewed as a generalization of the power iteration method for matrices or of the symmetric higher-order power method. Additionally, using fixed point analysis, we can characterize exactly which eigenpairs can and cannot be found by the method. Numerical examples are presented, including examples from an extension of the method to finding complex eigenpairs.

Keywords: tensor eigenvalues, E-eigenpairs, Z-eigenpairs, l2-eigenpairs, rank-1 approximation, symmetric higher-order power method (S-HOPM), shifted symmetric higher-order power method (SS-HOPM)

BibTeX:
@article{KoMa11,  
author = {Tamara G. Kolda and Jackson R. Mayo}, 
title = {Shifted Power Method for Computing Tensor Eigenpairs}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {32}, 
number = {4}, 
pages = {1095-1124}, 
month = {October}, 
year = {2011},
doi = {10.1137/100801482},
}

Version 1 (February 2011) was a short version with a different title. A revised short version was published in ICDM2011. Version 2 (September 2011) is the full version of this paper. Version 3 (January 2013) is the revised version accepted to JACM.

BibTeX:
@misc{SKG-arXiv-1102.5046,  
author = {C. Seshadhri and Ali Pinar and Tamara G. Kolda}, 
title = {An In-Depth Analysis of Stochastic {Kronecker} Graphs}, 
month = {February}, 
year = {2011},
eprint = {1102.5046},
eprintclass = {cs.SI},
}

BibTeX:
@incollection{DuKoKe11,  
author = {Daniel M. Dunlavy and Tamara G. Kolda and W. Philip Kegelmeyer}, 
title = {Multilinear Algebra for Analyzing Data with Multiple Linkages}, 
booktitle = {Graph Algorithms in the Language of Linear Algebra}, 
editor = {Jeremy Kepner and John Gilbert}, 
series = {Fundamentals of Algorithms}, 
publisher = {SIAM}, 
pages = {85--114}, 
year = {2011},
}

Abstract: Joint analysis of data from multiple sources has the potential to improve our understanding of the underlying structures in complex data sets. For instance, in restaurant recommendation systems, recommendations can be based on rating histories of customers. In addition to rating histories, customers' social networks (e.g., Facebook friendships) and restaurant categories information (e.g., Thai or Italian) can also be used to make better recommendations. The task of fusing data, however, is challenging since data sets can be incomplete and heterogeneous, i.e., data consist of both matrices, e.g., the person by person social network matrix or the restaurant by category matrix, and higher-order tensors, e.g., the "ratings" tensor of the form restaurant by meal by person. In this paper, we are particularly interested in fusing data sets with the goal of capturing their underlying latent structures. We formulate this problem as a coupled matrix and tensor factorization (CMTF) problem where heterogeneous data sets are modeled by fitting outer-product models to higher-order tensors and matrices in a coupled manner. Unlike traditional approaches solving this problem using alternating algorithms, we propose an all-at-once optimization approach called CMTF-OPT (CMTF-OPTimization), which is a gradient-based optimization approach for joint analysis of matrices and higher-order tensors. We also extend the algorithm to handle coupled incomplete data sets. Using numerical experiments, we demonstrate that the proposed all-at-once approach is more accurate than the alternating least squares approach.

BibTeX:
@inproceedings{AcKoDu11,  
author = {Evrim Acar and Tamara G. Kolda and Daniel M. Dunlavy}, 
title = {All-at-once Optimization for Coupled Matrix and Tensor Factorizations}, 
booktitle = {MLG'11: Proceedings of Mining and Learning with Graphs}, 
month = {August}, 
year = {2011},
eprint = {1105.3422},
}

Abstract: The tensor eigenproblem has many important applications, generating both mathematical and application-specific interest in the properties of tensor eigenpairs and methods for computing them. A tensor is an m-way array, generalizing the concept of a matrix (a 2-way array). Kolda and Mayo have recently introduced a generalization of the matrix power method for computing real-valued tensor eigenpairs of symmetric tensors. In this work, we present an efficient implementation of their algorithm, exploiting symmetry in order to save storage, data movement, and computation. For an application involving repeatedly solving the tensor eigenproblem for many small tensors, we describe how a GPU can be used to accelerate the computations. On an NVIDIA Tesla C 2050 (Fermi) GPU, we achieve 318 Gflops/s (31% of theoretical peak performance in single precision) on our test data set.

Keywords: tensors, tensor eigenvalues, GPU computing

BibTeX:
@inproceedings{BaKoPl11,  
author = {Grey Ballard and Tamara G. Kolda and Todd Plantenga}, 
title = {Efficiently Computing Tensor Eigenvalues on a {GPU}}, 
booktitle = {IPDPSW'11: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum}, 
eventtitle = {12th IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC-11)},
venue = {Anchorage, Alaska},
eventdate = {2011-05-16/2011-05-20}, 
publisher = {IEEE Computer Society}, 
pages = {1340--1348}, 
month = {May}, 
year = {2011},
doi = {10.1109/IPDPS.2011.287},
}

BibTeX:
@article{SIAM-News-Top-Ten,  
author = {Tamara G. Kolda and Virginia J. Torczon}, 
title = {Top Ten Ways to Lose an Audience}, 
journal = {SIAM News}, 
volume = {44}, 
number = {3}, 
month = {April}, 
year = {2011},	
url = {http://www.siam.org/news/news.php?id=1876},
}

Abstract: Tensors are multi-way arrays, and the CANDECOMP/PARAFAC (CP) tensor factorization has found application in many different domains. The CP model is typically fit using a least squares objective function, which is a maximum likelihood estimate under the assumption of independent and identically distributed (i.i.d.) Gaussian noise. We demonstrate that this loss function can be highly sensitive to non-Gaussian noise. Therefore, we propose a loss function based on the 1-norm because it can accommodate both Gaussian and grossly non-Gaussian perturbations. We also present an alternating majorization-minimization (MM) algorithm for fitting a CP model using our proposed loss function (CPAL1) and compare its performance to the workhorse algorithm for fitting CP models, CP alternating least squares (CPALS).

BibTeX:
@techreport{SAND2011-1877,  
author = {Eric C. Chi and Tamara G. Kolda}, 
title = {Making Tensor Factorizations Robust to Non-{Gaussian} Noise}, 
number = {SAND2011-1877}, 
institution = {Sandia National Laboratories}, 
month = {March}, 
year = {2011},
doi = {10.2172/1011706},	
url = {http://www.osti.gov/scitech/biblio/1011706},
urldate = {2014-04-17},
}

BibTeX:
@misc{COMET,  
author = {Justin D. Basilico and M. Arthur Munson and Tamara G. Kolda and Kevin R. Dixon and W. Philip Kegelmeyer}, 
title = {{COMET}: A Recipe for Learning and Using Large Ensembles on Massive Data}, 
month = {March}, 
year = {2011},
eprint = {1103.2068},
eprintclass = {cs.LG},
}

Abstract: The problem of incomplete data---i.e., data with missing or unknown values---in multi-way arrays is ubiquitous in biomedical signal processing, network traffic analysis, bibliometrics, social network analysis, chemometrics, computer vision, communication networks, etc. We consider the problem of how to factorize data sets with missing values with the goal of capturing the underlying latent structure of the data and possibly reconstructing missing values (i.e., tensor completion). We focus on one of the most well-known tensor factorizations that captures multi-linear structure, CANDECOMP/PARAFAC~(CP). In the presence of missing data, CP can be formulated as a weighted least squares problem that models only the known entries. We develop an algorithm called CP-WOPT (CP Weighted OPTimization) that uses a first-order optimization approach to solve the weighted least squares problem. Based on extensive numerical experiments, our algorithm is shown to successfully factorize tensors with noise and up to 99% missing data. A unique aspect of our approach is that it scales to sparse large-scale data, e.g., 1000 x 1000 x 1000 with five million known entries (0.5% dense). We further demonstrate the usefulness of CP-WOPT on two real-world applications: a novel EEG (electroencephalogram) application where missing data is frequently encountered due to disconnections of electrodes and the problem of modeling computer network traffic where data may be absent due to the expense of the data collection process.

Keywords: missing data, incomplete data, tensor factorization, CANDECOMP, PARAFAC, optimization

BibTeX:
@article{AcDuKoMo11,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda and Morten M{\o}rup}, 
title = {Scalable Tensor Factorizations for Incomplete Data}, 
journal = {Chemometrics and Intelligent Laboratory Systems}, 
issuetitle = {Special Issue on Multiway and Multiset Data Analysis}, 
volume = {106}, 
number = {1}, 
pages = {41--56}, 
month = {March}, 
year = {2011},
doi = {10.1016/j.chemolab.2010.08.004},
}

Abstract: The data in many disciplines such as social networks, web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this paper, we consider the problem of temporal link prediction: Given link data for times 1 through T, can we predict the links at time T+1? If our data has underlying periodic structure, can we predict out even further in time, i.e., links at time T+2, T+3, etc.? In this paper, we consider bipartite graphs that evolve over time and consider matrix- and tensor-based methods for predicting future links. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem. Additionally, we show that tensor-based techniques are particularly effective for temporal data with varying periodic patterns.

Keywords: link mining, link prediction, evolution, tensor factorization, CANDECOMP, PARAFAC

BibTeX:
@article{DuKoAc11,  
author = {Daniel M. Dunlavy and Tamara G. Kolda and Evrim Acar}, 
title = {Temporal Link Prediction using Matrix and Tensor Factorizations}, 
journal = {ACM Transactions on Knowledge Discovery from Data}, 
issuetitle = {Special Issue on Large-scale Data Mining: Theory and Applications}, 
volume = {5}, 
number = {2}, 
pages = {10 (27 pages)}, 
month = {February}, 
year = {2011},
doi = {10.1145/1921632.1921636},
}

Abstract: Tensor decompositions are higher-order analogues of matrix decompositions and have proven to be powerful tools for data analysis. In particular, we are interested in the canonical tensor decomposition, otherwise known as CANDECOMP/PARAFAC (CP), which expresses a tensor as the sum of component rank-one tensors and is used in a multitude of applications such as chemometrics, signal processing, neuroscience, and web analysis. The task of computing CP, however, can be difficult. The typical approach is based on alternating least squares (ALS) optimization, but it is not accurate in the case of overfactoring. High accuracy can be obtained by using nonlinear least squares (NLS) methods; the disadvantage is that NLS methods are much slower than ALS. In this paper, we propose the use of gradient-based optimization methods. We discuss the mathematical calculation of the derivatives and show that they can be computed efficiently, at the same cost as one iteration of ALS. Computational experiments demonstrate that the gradient-based optimization methods are more accurate than ALS and faster than NLS in terms of total computation time.

Keywords: tensor decomposition, tensor factorization, CANDECOMP, PARAFAC, optimization

Online version published January 2011.

BibTeX:
@article{AcDuKo11,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda}, 
title = {A Scalable Optimization Approach for Fitting Canonical Tensor Decompositions}, 
journal = {Journal of Chemometrics}, 
volume = {25}, 
number = {2}, 
pages = {67--86}, 
month = {February}, 
year = {2011},
doi = {10.1002/cem.1335},
}

Abstract: Tensors are multi-way arrays, and the Candecomp/Parafac (CP) tensor factorization has found application in many different domains. The CP model is typically fit using a least squares objective function, which is a maximum likelihood estimate under the assumption of i.i.d. Gaussian noise. We demonstrate that this loss function can actually be highly sensitive to non-Gaussian noise. Therefore, we propose a loss function based on the 1-norm because it can accommodate both Gaussian and grossly non-Gaussian perturbations. We also present an alternating majorization-minimization algorithm for fitting a CP model using our proposed loss function.

Keywords: CANDECOMP, PARAFAC, 1-norm, non-Gaussian noise

Contributed paper at the NIPS Workshop on Tensors, Kernels, and Machine Learning, Whistler, BC, Canada, December 10, 2010

BibTeX:
@inproceedings{arXiv_1010.3043,  
author = {Eric C. Chi and Tamara G. Kolda}, 
title = {Making Tensor Factorizations Robust to Non-{G}aussian Noise}, 
booktitle = {NIPS Workshop on Tensors, Kernels, and Machine Learning},
venue = {Whistler, BC},
eventdate = {2010-12-10}, 
month = {October}, 
year = {2010},
eprint = {1010.3043},
eprintclass = {math.NA},
}

BibTeX:
@inproceedings{BallardStudentPaper2010,  
author = {Grey Ballard and Tamara G. Kolda and Todd Plantenga}, 
title = {Efficiently Computing Tensor Eigenvalues on a {GPU}}, 
booktitle = {CSRI Summer Proceedings 2010, Technical Report SAND2010-8783P, Sandia National Laboratories}, 
editor = {Eric C. Cyr and S. Scott Collis}, 
pages = {59--75}, 
year = {2010},	
url = {http://csri.sandia.gov/Proceedings/CSRI-Summer-2010.pdf},
}

BibTeX:
@misc{arXiv_1007.1267,  
author = {Tamara G. Kolda and Jackson R. Mayo}, 
title = {Shifted Power Method for Computing Tensor Eigenpairs}, 
month = {July}, 
year = {2011},
eprint = {1007.1267},
eprintclass = {math.NA},
}

BibTeX:
@misc{arXiv_1005.4006,  
author = {Daniel M. Dunlavy and Tamara G. Kolda and Evrim Acar}, 
title = {Temporal Link Prediction using Matrix and Tensor Factorizations}, 
month = {May}, 
year = {2010},
note = {revised June 2010},
eprint = {1005.4006},
eprintclass = {math.NA},
}

BibTeX:
@misc{arXiv_1005.2197,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda and Morten M{\o}rup}, 
title = {Scalable Tensor Factorizations for Incomplete Data}, 
month = {May}, 
year = {2010},
eprint = {1005.2197},
eprintclass = {math.NA},
}

Abstract: The problem of missing data is ubiquitous in domains such as biomedical signal processing, network traffic analysis, bibliometrics, social network analysis, chemometrics, computer vision, and communication networks---all domains in which data collection is subject to occasional errors. Moreover, these data sets can be quite large and have more than two axes of variation, e.g., sender, receiver, time. Many applications in those domains aim to capture the underlying latent structure of the data; in other words, they need to factorize data sets with missing entries. If we cannot address the problem of missing data, many important data sets will be discarded or improperly analyzed. Therefore, we need a robust and scalable approach for factorizing multi-way arrays (i.e., tensors) in the presence of missing data. We focus on one of the most well-known tensor factorizations, CANDECOMP/PARAFAC (CP), and formulate the CP model as a weighted least squares problem that models only the known entries. We develop an algorithm called CP-WOPT (CP Weighted OPTimization) using a first-order optimization approach to solve the weighted least squares problem. Based on extensive numerical experiments, our algorithm is shown to successfully factor tensors with noise and up to 70% missing data. Moreover, our approach is significantly faster than the leading alternative and scales to larger problems. To show the real-world usefulness of CP-WOPT, we illustrate its applicability on a novel EEG (electroencephalogram) application where missing data is frequently encountered due to disconnections of electrodes.

Keywords: missing data, tensor factorization, CANDECOMP, PARAFAC, optimization

BibTeX:
@inproceedings{AcDuKoMo10,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda and Morten M{\o}rup}, 
title = {Scalable Tensor Factorizations with Missing Data}, 
booktitle = {SDM10: Proceedings of the 2010 SIAM International Conference on Data Mining},
venue = {Columbus, Ohio},
eventdate = {2010-04-29/2010-05-01}, 
pages = {701--712}, 
year = {2010},
doi = {10.1137/1.9781611972801.61},
}

Abstract: Many optimization problems 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 presents a study of heuristic algorithms that address the more difficult problem of general nonlinear constraints where derivatives for objective or constraint functions are unavailable. We focus on penalty methods that use GSS to solve a sequence of linearly-constrained problems, numerically comparing different penalty functions. A classical choice for penalizing constraint violations is 2^2, the squared 2 norm, which has advantages for derivative-based optimization methods. In our numerical tests, however, we show that exact penalty functions based on the 1, 2, and infty norms converge to good approximate solutions more quickly and thus are attractive alternatives. Unfortunately, exact penalty functions are nondifferentiable and consequently degrade the final solution accuracy, so we also consider smoothed variants. Smoothed-exact penalty functions are attractive because they retain the differentiability of the original problem. Numerically, they are a compromise between exact and 2^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 our focus is on optimization problems that are characterized by expensive function evaluations, reducing the number of function evaluations is paramount, and the numerical results of this paper suggest that exact and smoothed-exact penalty functions are well-suited to this task.

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

BibTeX:
@article{GrKo10,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {Nonlinearly-constrained Optimization Using Heuristic Penalty Methods and Asynchronous Parallel Generating Set Search}, 
journal = {Applied Mathematics Research eXpress}, 
volume = {25}, 
number = {5}, 
pages = {36--62}, 
month = {October}, 
year = {2010},
doi = {10.1093/amrx/abq003},
}

Abstract: We present Poblano v1.0, a Matlab toolbox for solving gradient-based unconstrained optimization problems. Poblano implements three optimization methods (nonlinear conjugate gradients, limited- memory BFGS, and truncated Newton) that require only first order derivative information. In this paper, we describe the Poblano methods, provide numerous examples on how to use Poblano, and present results of Poblano used in solving problems from a standard test collection of unconstrained optimization problems.

Keywords: tensor decomposition, tensor factorization, CANDECOMP, PARAFAC, optimization

BibTeX:
@techreport{SAND2010-1422,  
author = {Daniel M. Dunlavy and Tamara G. Kolda and Evrim Acar}, 
title = {Poblano v1.0: A Matlab Toolbox for Gradient-Based Optimization}, 
number = {SAND2010-1422}, 
institution = {Sandia National Laboratories}, 
month = {March}, 
year = {2010},
doi = {10.2172/989350},	
url = {http://www.osti.gov/scitech/biblio/989350},
urldate = {2014-04-17},
}

Abstract: The data in many disciplines such as social networks, web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this paper, we consider the problem of temporal link prediction: Given link data for time periods 1 through T, can we predict the links in time period T +1? Specifically, we look at bipartite graphs changing over time and consider matrix- and tensorbased methods for predicting links. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural threedimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrixand tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem.

Keywords: link mining, link prediction, evolution, tensor factorization, CANDECOMP, PARAFAC

Presented at LDMTA'09: ICDM'09 Workshop on Large Scale Data Mining Theory and Applications.

BibTeX:
@inproceedings{AcDuKo09,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda}, 
title = {Link Prediction on Evolving Data using Matrix and Tensor Factorizations}, 
booktitle = {ICDMW'09: Proceedings of the 2009 IEEE International Conference on Data Mining Workshops},
venue = {Miami, FL},
eventdate = {2009-12-06}, 
pages = {262--269}, 
month = {December}, 
year = {2009},
doi = {10.1109/ICDMW.2009.54},
}

BibTeX:
@techreport{SAND2009-6764,  
author = {Evrim Acar and Daniel M. Dunlavy and Morten M{\o}rup and Tamara G. Kolda}, 
title = {Scalable Tensor Factorizations with Missing Data}, 
number = {SAND2009-6764}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2009},
}

Abstract: BadRank is a method for detecting spam web sites, based on the premise that a page is spam if it points to another spam page; i.e., the BadRank score of a page is the weighted sum of the BadRank scores of the pages that it links to. BadRank is an important tool in spam detection. We consider the mathematical structure of BadRank, showing how it can be modified to guarantee that the iterates converge. Additionally, we consider methods for incorporating knowledge about trusted (known non-spam) sites into the BadRank calculation by changing the underlying iteration matrix. The effectiveness of BadRank in web spam detection is demonstrated in a statistically significant evaluation on the WEBSPAM-UK2007 data set.

Keywords: PageRank, Web Spam, Distrust

BibTeX:
@techreport{SAND2009-6670,  
author = {Tamara G. Kolda and Michael J. Procopio}, 
title = {Generalized BadRank with Graduated Trust}, 
number = {SAND2009-6670}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2009},
}

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)

© 2009 Society for Industrial and Applied Mathematics

BibTeX:
@article{KoBa09,  
author = {Tamara G. Kolda and Brett W. Bader}, 
title = {Tensor Decompositions and Applications}, 
journal = {SIAM Review}, 
volume = {51}, 
number = {3}, 
pages = {455--500}, 
month = {September}, 
year = {2009},
doi = {10.1137/07070111X},
}

Abstract: In this paper we explore hybrid parallel global optimization using DIRECT and asynchronous generating 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. DIRECT 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 starting point. Using a set of global optimization test problems, we compare the parallel performance of DIRECT and GSS with hybrids that combine the two methods. Our experiments suggest that 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 find 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

Online version published August 2009.

BibTeX:
@article{GrKo10a,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {Asynchronous Parallel Hybrid Optimization Combining {DIRECT} and {GSS}}, 
journal = {Optimization Methods and Software}, 
volume = {25}, 
number = {5}, 
pages = {797-817}, 
month = {October}, 
year = {2010},
doi = {10.1080/10556780903039893},
}

BibTeX:
@techreport{SAND2009-0857,  
author = {Evrim Acar and Tamara G. Kolda and Daniel M. Dunlavy}, 
title = {An Optimization Approach for Fitting Canonical Tensor Decompositions}, 
number = {SAND2009-0857}, 
institution = {Sandia National Laboratories}, 
month = {February}, 
year = {2009},
doi = {10.2172/978916},	
url = {http://www.osti.gov/scitech/biblio/978916},
urldate = {2014-04-17},
}

Abstract: This white paper is a response to a recent report on cybersecurity submitted to the U.S. Department of Energy (Catlett, 2008). We discuss what we see as some of the major mathematical challenges in cybersecurity. The document is not intended to be comprehensive, but rather the articulation of a few key themes. We have organized our thoughts into three challenge areas: modeling large-scale networks, threat discovery, and network dynamics.

BibTeX:
@techreport{SAND2009-0805,  
author = {Daniel M. Dunlavy and Bruce Hendrickson and Tamara G. Kolda}, 
title = {Mathematical Challenges in Cybersecurity}, 
number = {SAND 2009-0805}, 
institution = {Sandia National Laboratories}, 
month = {February}, 
year = {2009},
}

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.

Keywords: data mining, tensor decomposition, Tucker decomposition, sparse data

Best Theoretical/Algorithms Paper Award, IEEE International Conference on Data Mining (ICDM), Pisa, Italy, Dec. 2008

BibTeX:
@inproceedings{KoSu08,  
author = {Tamara G. Kolda and Jimeng Sun}, 
title = {Scalable Tensor Decompositions for Multi-aspect Data Mining}, 
booktitle = {ICDM 2008: Proceedings of the 8th IEEE International Conference on Data Mining},
venue = {Pisa, Italy},
eventdate = {2008-12-15/2008-12-19}, 
pages = {363--372}, 
year = {2008},
doi = {10.1109/ICDM.2008.89},
}

BibTeX:
@inproceedings{CASTA2008,  
author = {Evrim Acar and Daniel M. Dunlavy and Tamara G. Kolda}, 
title = {CPOPT: Optimization for Fitting {CANDECOMP/PARAFAC} Models (extended abstact)}, 
booktitle = {CASTA 2008: Workshop on Computational Algebraic Statistics, Theories and Applications},
venue = {Kyoto, Japan},
eventdate = {2008-12-10/2008-12-12}, 
year = {2008},
}

BibTeX:
@techreport{SAND2008-6553,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {Asynchronous Parallel Hybrid Optimization Combining {DIRECT} and {GSS}}, 
number = {SAND2008-6553}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2008},
}

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 optimization algorithm. It is a deterministic algorithm that samples the space following a scheme that is justifiable theoretically in case of Lipschitz continuous functions. In practice, DIRECT has proven to be efficient, with respect to the number of function evaluations, in finding 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 available 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.

BibTeX:
@techreport{SAND2008-5844,  
author = {Noam Goldberg and Tamara G. Kolda and Ann S. Yoshimura}, 
title = {Concurrent Optimization with {DUET}: {DIRECT} Using External Trial Points}, 
number = {SAND2008-5844}, 
institution = {Sandia National Laboratories}, 
month = {September}, 
year = {2008},
}

BibTeX:
@incollection{SAND2008-6109,  
author = {Tamara G. Kolda and Brett W. Bader}, 
title = {Multi-way Data Analysis and Applications (extended abstract)}, 
booktitle = {Proceedings of the 2008 Sandia Workshop on Data Mining and Data Analysis}, 
editor = {James M. Brandt and Daniel M. Dunlavy and Ann C. Gentile}, 
number = {SAND2008-6109}, 
publisher = {Sandia National Laboratories}, 
pages = {42--45}, 
month = {September}, 
year = {2008},
}

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

BibTeX:
@article{GrKoLe08,  
author = {Joshua D. Griffin and Tamara G. Kolda and Robert Michael Lewis}, 
title = {Asynchronous Parallel Generating Set Search For Linearly-Constrained Optimization}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {30}, 
number = {4}, 
pages = {1892--1924}, 
month = {May}, 
year = {2008},
doi = {10.1137/060664161},
}

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

BibTeX:
@article{FoReKeDe08,  
author = {K. R. Fowler and J. P. Reese and C. E. Kees and J. E. {Dennis, Jr.} and C. T. Kelley and C. T. Miller and C. Audet and A. J. Booker and G. Couture and R. W. Darwin and M. W. Farthing and D. E. Finkel and J. M. Gablonsky and G. Gray and T. G. Kolda}, 
title = {A Comparison of Derivative-Free Optimization Methods for Groundwater Supply and Hydraulic Capture Community Problems}, 
journal = {Advances in Water Resources}, 
volume = {31}, 
number = {5}, 
pages = {743--757}, 
month = {May}, 
year = {2008},
doi = {10.1016/j.advwatres.2008.01.010},
}

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

BibTeX:
@article{BrAcKo08,  
author = {Rasmus Bro and Evrim Acar and Tamara G. Kolda}, 
title = {Resolving the Sign Ambiguity in the Singular Value Decomposition}, 
journal = {Journal of Chemometrics}, 
volume = {22}, 
number = {2}, 
pages = {135--140}, 
month = {February}, 
year = {2008},
doi = {10.1002/cem.1122},
}

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

BibTeX:
@article{BaKo07,  
author = {Brett W. Bader and Tamara G. Kolda}, 
title = {Efficient {MATLAB} Computations with Sparse and Factored Tensors}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {30}, 
number = {1}, 
pages = {205--231}, 
month = {December}, 
year = {2007},
doi = {10.1137/060676489},
}

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.

BibTeX:
@inproceedings{SeKoKeGr07,  
author = {Teresa M. Selee and Tamara G. Kolda and W. Philip Kegelmeyer and Joshua D. Griffin}, 
title = {Extracting Clusters from Large Datasets with Multiple Similarity Measures Using {IMSCAND}}, 
booktitle = {CSRI Summer Proceedings 2007}, 
editor = {Michael L. Parks and S. Scott Collis}, 
publisher = {Tech. Rep. SAND2007-7977, Sandia National Laboratories}, 
pages = {87--103}, 
month = {December}, 
year = {2007},	
url = {http://www.cs.sandia.gov/CSRI/Proceedings/CSRI2007.pdf},
}

BibTeX:
@techreport{SAND2007-6702,  
author = {Tamara G. Kolda and Brett W. Bader}, 
title = {Tensor Decompositions and Applications}, 
number = {SAND2007-6702}, 
institution = {Sandia National Laboratories}, 
month = {November}, 
year = {2007},
}

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.

BibTeX:
@inproceedings{BaHaKo07,  
author = {Brett W. Bader and Richard A. Harshman and Tamara G. Kolda}, 
title = {Temporal Analysis of Semantic Graphs using {ASALSAN}}, 
booktitle = {ICDM 2007: Proceedings of the 7th IEEE International Conference on Data Mining},
venue = {Omaha, NE},
eventdate = {2007-10-28/2007-10-31}, 
pages = {33-42}, 
year = {2007},
doi = {10.1109/ICDM.2007.54},
}

BibTeX:
@techreport{SAND2007-6422,  
author = {Rasmus Bro and Evrim Acar and Tamara G. Kolda}, 
title = {Resolving the Sign Ambiguity in the Singular Value Decomposition}, 
number = {SAND2007-6422}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2007},
doi = {10.2172/920802},	
url = {http://www.osti.gov/scitech/biblio/920802},
urldate = {2014-04-17},
}

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

BibTeX:
@inproceedings{ChBaKoAb07,  
author = {Peter A. Chew and Brett W. Bader and Tamara G. Kolda and Ahmed Abdelali}, 
title = {Cross-language Information Retrieval using {PARAFAC2}}, 
booktitle = {KDD '07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
venue = {San Jose, CA},
eventdate = {2007-08-12/2007-08-15}, 
publisher = {ACM}, 
pages = {143-152}, 
year = {2007},
doi = {10.1145/1281192.1281211},
}

BibTeX:
@article{SIAM-News-BGCE,  
author = {Tamara G. Kolda and U. R\"ude}, 
title = {First {BGCE} Student Prize in CSE}, 
journal = {SIAM News}, 
volume = {40}, 
number = {5}, 
month = {June}, 
year = {2007},	
url = {http://www.siam.org/news/news.php?id=1130},
}

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.

BibTeX:
@inproceedings{FaKoSu07,  
author = {Christos Faloutsos and Tamara G. Kolda and Jimeng Sun}, 
title = {Mining Large Graphs and Streams using Matrix and Tensor Tools (extended abstract)}, 
booktitle = {SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data},
venue = {Beijing, China},
eventdate = {2007-06-11/2007-06-14}, 
publisher = {ACM}, 
pages = {1174}, 
year = {2007},
doi = {10.1145/1247480.1247647},
}

BibTeX:
@techreport{SAND2007-3257,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {Nonlinearly-constrained Optimization using Asynchronous Parallel Generating Set Search}, 
number = {SAND2007-3257}, 
institution = {Sandia National Laboratories}, 
month = {May}, 
year = {2007},
doi = {10.2172/909393},	
url = {http://www.osti.gov/scitech/biblio/909393},
urldate = {2014-04-17},
}

BibTeX:
@techreport{SAND2007-2706,  
author = {Peter A. Chew and Brett W. Bader and Tamara G. Kolda and Ahmed Abdelali}, 
title = {Cross-language Information Retrieval using {PARAFAC2}}, 
number = {SAND2007-2706}, 
institution = {Sandia National Laboratories}, 
month = {May}, 
year = {2007},
doi = {10.2172/908061},	
url = {http://www.osti.gov/scitech/biblio/908061},
urldate = {2014-04-17},
}

BibTeX:
@techreport{SAND2006-7744,  
author = {Brett W. Bader and Richard Harshman and Tamara G. Kolda}, 
title = {Pattern Analysis of Directed Graphs Using {DEDICOM}: An Application to Enron Email}, 
number = {SAND2006-7744}, 
institution = {Sandia National Laboratories}, 
month = {December}, 
year = {2006},
}

BibTeX:
@techreport{SAND2006-7592,  
author = {Brett W. Bader and Tamara G. Kolda}, 
title = {Efficient {MATLAB} Computations with Sparse and Factored Tensors}, 
number = {SAND2006-7592}, 
institution = {Sandia National Laboratories}, 
month = {December}, 
year = {2006},
doi = {10.2172/897641},	
url = {http://www.osti.gov/scitech/biblio/897641},
urldate = {2014-04-17},
}

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

BibTeX:
@article{BaKo06,  
author = {Brett W. Bader and Tamara G. Kolda}, 
title = {Algorithm 862: {MATLAB} Tensor Classes for Fast Algorithm Prototyping}, 
journal = {ACM Transactions on Mathematical Software}, 
volume = {32}, 
number = {4}, 
pages = {635--653}, 
month = {December}, 
year = {2006},
doi = {10.1145/1186785.1186794},
}

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

BibTeX:
@article{KoLeTo06,  
author = {Tamara G. Kolda and Robert Michael Lewis and Virginia Torczon}, 
title = {Stationarity Results for Generating Set Search for Linearly Constrained Optimization}, 
journal = {SIAM Journal on Optimization}, 
volume = {17}, 
number = {4}, 
pages = {943--968}, 
month = {November}, 
year = {2006},
doi = {10.1137/S1052623403433638},
}

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

BibTeX:
@article{GrKo06,  
author = {Genetha A. Gray and Tamara G. Kolda}, 
title = {Algorithm 856: {APPSPACK} 4.0: Asynchronous Parallel Pattern Search for Derivative-Free Optimization}, 
journal = {ACM Transactions on Mathematical Software}, 
volume = {32}, 
number = {3}, 
pages = {485--507}, 
month = {September}, 
year = {2006},
doi = {10.1145/1163641.1163647},
}

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.

BibTeX:
@techreport{SAND2006-4055,  
author = {Michael S. Eldred and Anthony A. Giunta and Shannon L. Brown and Brian M. Adams and Daniel M. Dunlavy and John P. Eddy and David M. Gay and Josh D. Griffin and William E. Hart and Patty D. Hough and Tammy G. Kolda and Monica L. Martinez-Canales and Laura P. Swiler and Jean-Paul Watson and Pamela J. Williams}, 
title = {{DAKOTA}, a Multilevel Parallel Object-oriented Framework for Design Optimization, Parameter Estimation, Uncertainty Quantification, and Sensitivity Analysis: Version 4.0 Reference Manual}, 
number = {SAND2006-4055}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2006},
doi = {10.2172/895073},	
url = {http://www.osti.gov/scitech/biblio/895073},
urldate = {2014-04-17},
}

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

BibTeX:
@techreport{SAND2006-5315,  
author = {Tamara G. Kolda and Robert Michael Lewis and V. Torczon}, 
title = {A Generating Set Direct Search Augmented {Lagrangian} Algorithm for Optimization with a Combination of General and Linear Constraints}, 
number = {SAND2006-5315}, 
institution = {Sandia National Laboratories}, 
month = {August}, 
year = {2006},
doi = {10.2172/893121},	
url = {http://www.osti.gov/scitech/biblio/893121},
urldate = {2014-04-17},
}

BibTeX:
@techreport{SAND2006-4621,  
author = {Joshua D. Griffin and Tamara G. Kolda and Robert Michael Lewis}, 
title = {Asynchronous Parallel Generating Set Search For Linearly-Constrained Optimization}, 
number = {SAND2006-4621}, 
institution = {Sandia National Laboratories}, 
month = {August}, 
year = {2006},
doi = {10.2172/891372},	
url = {http://www.osti.gov/scitech/biblio/891372},
urldate = {2014-04-17},
}

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

BibTeX:
@inproceedings{ICMS2006,  
author = {Joshua D. Griffin and Tamara G. Kolda}, 
title = {A Parallel, Asynchronous Method for Derivative-Free Nonlinear Programs (extended abstract)}, 
booktitle = {Mathematical Software - ICMS 2006}, 
eventtitle = {Second International Congress on Mathematical Software},
venue = {Castro Urdiales, Spain},
eventdate = {2006-09-01/2006-09-03}, 
series = {Lecture Notes in Computer Science}, 
volume = {4151}, 
publisher = {Springer Berlin Heidelberg}, 
pages = {260--262}, 
year = {2006},
doi = {10.1007/11832225_26},
}

BibTeX:
@techreport{SAND2006-2161,  
author = {Brett W. Bader and Richard Harshman and Tamara G. Kolda}, 
title = {Temporal Analysis of Social Networks using Three-way {DEDICOM}}, 
number = {SAND2006-2161}, 
institution = {Sandia National Laboratories}, 
month = {April}, 
year = {2006},
doi = {10.2172/887253},	
url = {http://www.osti.gov/scitech/biblio/887253},
urldate = {2014-04-17},
}

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

BibTeX:
@techreport{SAND2006-2079,  
author = {Daniel M. Dunlavy and Tamara G. Kolda and W. Philip Kegelmeyer}, 
title = {Multilinear Algebra for Analyzing Data with Multiple Linkages}, 
number = {SAND2006-2079}, 
institution = {Sandia National Laboratories}, 
month = {April}, 
year = {2006},
doi = {10.2172/883132},	
url = {http://www.osti.gov/scitech/biblio/883132},
urldate = {2014-04-17},
}

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

There is an error in Example 3.3.

BibTeX:
@techreport{SAND2006-2081,  
author = {Tamara G. Kolda}, 
title = {Multilinear Operators for Higher-order Decompositions}, 
number = {SAND2006-2081}, 
institution = {Sandia National Laboratories}, 
month = {April}, 
year = {2006},
doi = {10.2172/923081},	
url = {http://www.osti.gov/scitech/biblio/923081},
urldate = {2014-04-17},
}

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

BibTeX:
@inproceedings{KoBa06,  
author = {Tamara Kolda and Brett Bader}, 
title = {The {TOPHITS} Model for Higher-order Web Link Analysis}, 
booktitle = {Proceedings of Link Analysis, Counterterrorism and Security 2006}, 
eventtitle = {Sixth SIAM International Conference on Data Mining, SDM06},
venue = {Bethesda, MD},
eventdate = {2006-04-22}, 
year = {2006},	
url = {http://www.siam.org/meetings/sdm06/workproceed/Link Analysis/21Tamara_Kolda_SIAMLACS.pdf},
}

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

BibTeX:
@article{Ko05,  
author = {Tamara G. Kolda}, 
title = {Revisiting Asynchronous Parallel Pattern Search for Nonlinear Optimization}, 
journal = {SIAM Journal on Optimization}, 
volume = {16}, 
number = {2}, 
pages = {563--586}, 
month = {December}, 
year = {2005},
doi = {10.1137/040603589},
}

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.

BibTeX:
@techreport{SAND2005-6864,  
author = {Brett W. Bader and Roger P. Pawlowski and Tamara G. Kolda}, 
title = {Robust Large-scale Parallel Nonlinear Solvers for Simulations}, 
number = {SAND2005-6864}, 
institution = {Sandia National Laboratories}, 
month = {November}, 
year = {2005},
doi = {10.2172/876345},	
url = {http://www.osti.gov/scitech/biblio/876345},
urldate = {2014-04-17},
}

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.

BibTeX:
@inproceedings{KoBaKe05,  
author = {Tamara G. Kolda and Brett W. Bader and Joseph P. Kenny}, 
title = {Higher-Order Web Link Analysis Using Multilinear Algebra}, 
booktitle = {ICDM 2005: Proceedings of the 5th IEEE International Conference on Data Mining},
venue = {Houston, TX},
eventdate = {2005-11-27/2005-11-30}, 
pages = {242--249}, 
year = {2005},
doi = {10.1109/ICDM.2005.77},
}

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.

BibTeX:
@article{HeBaHoHo05,  
author = {Michael A. Heroux and Roscoe A. Bartlett and Vicki E. Howle and Robert J. Hoekstra and Jonathan J. Hu and Tamara G. Kolda and Richard B. Lehoucq and Kevin R. Long and Roger P. Pawlowski and Eric T. Phipps and Andrew G. Salinger and Heidi K. Thornquist and Ray S. Tuminaro and James M. Willenbring and Alan Williams and Kendall S. Stanley}, 
title = {An Overview of the {Trilinos} Project}, 
journal = {ACM Transactions on Mathematical Software}, 
volume = {31}, 
number = {3}, 
pages = {397--423}, 
month = {September}, 
year = {2005},
doi = {10.1145/1089014.1089021},
}

BibTeX:
@techreport{SAND2005-4548,  
author = {Tamara G. Kolda and Brett W. Bader and Joseph P. Kenny}, 
title = {Higher-Order Web Link Analysis Using Multilinear Algebra}, 
number = {SAND2005-4548}, 
institution = {Sandia National Laboratories}, 
month = {July}, 
year = {2005},
doi = {10.2172/974401},	
url = {http://www.osti.gov/scitech/biblio/974401},
urldate = {2014-04-17},
}

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

BibTeX:
@techreport{SAND2005-6648,  
author = {T. Kolda and others}, 
title = {Data Sciences Technology for Homeland Security Information Management and Knowledge Discovery: DHS Workshop on Data Sciences},
venue = {Alexandria, VA},
eventdate = {2004-09-22/2004-09-23}, 
number = {SAND2005-6648}, 
institution = {Sandia National Laboratories}, 
month = {January}, 
year = {2005},
}

BibTeX:
@incollection{Complexities-2005,  
author = {Tamara G. Kolda}, 
title = {An Unexpected Turn}, 
booktitle = {Complexities: Women in Mathematics}, 
editor = {Bettye Anne Case and Anne M. Leggett}, 
publisher = {Princeton University Press}, 
pages = {388--390}, 
month = {January}, 
year = {2005},
}

BibTeX:
@techreport{SAND2004-6391,  
author = {Genetha A. Gray and Tamara G. Kolda}, 
title = {{APPSPACK 4.0}: Asynchronous Parallel Pattern Search for Derivative-free Optimization}, 
number = {SAND2004-6391}, 
institution = {Sandia National Laboratories}, 
month = {December}, 
year = {2004},
doi = {10.2172/974891},	
url = {http://www.osti.gov/scitech/biblio/974891},
urldate = {2014-04-17},
}

BibTeX:
@techreport{SAND2004-5187,  
author = {Brett W. Bader and Tamara G. Kolda}, 
title = {{MATLAB} Tensor Classes for Fast Algorithm Prototyping}, 
number = {SAND2004-5187}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2004},
doi = {10.2172/974890},	
url = {http://www.osti.gov/scitech/biblio/974890},
urldate = {2014-04-17},
}

Abstract: We examine the problem of transmembrane protein structure determination. Like many other questions that arise in biological research, this problem cannot be addressed by traditional laboratory experimentation alone. An approach that integrates experiment and computation is required. We investigate a procedure which states the transmembrane protein structure determination problem as a bound constrained optimization problem using a special empirical scoring function, called Bundler, as the objective function. In this paper, we describe the optimization problem and some of its mathematical properties. We compare and contrast results obtained using two different derivative free optimization algorithms.

Keywords: optimization, computational biology, nonlinear programming, parallel algorithm, protein structure, Bundler scoring function

BibTeX:
@article{GrKoSaYo04,  
author = {Genetha Anne Gray and Tamara G. Kolda and Kenneth L. Sale and Malin M. Young}, 
title = {Optimizing an Empirical Scoring Function for Transmembrane Protein Structure Determination}, 
journal = {INFORMS Journal on Computing}, 
issuetitle = {Special Issue on Computational Molecular Biology/Bioinformatics}, 
volume = {16}, 
number = {4}, 
pages = {406--418}, 
year = {2004},
doi = {10.1287/ijoc.1040.0102},
}

BibTeX:
@techreport{SAND2004-3487,  
author = {Brett W. Bader and Tamara G. Kolda}, 
title = {A Preliminary Report on the Development of {MATLAB} Tensor Classes for Fast Algorithm Prototyping}, 
number = {SAND2004-3487}, 
institution = {Sandia National Laboratories}, 
month = {July}, 
year = {2004},
doi = {10.2172/974887},	
url = {http://www.osti.gov/scitech/biblio/974887},
urldate = {2014-04-17},
}

Abstract: Validated, internal state variable constitutive models are developed to model the complex multistage forging process and predict the final forging strength and microstructure. Optimization methodologies are then used on a high performance, parallel computer to design the forging dies and temperatures that would meet minimum and maximum strength requirements and result in maximum strength uniformity. Each node on the parallel computer solves a unique finite element simulation including parametric meshing, post-processing and metric determination. Nine shape parameters and one process parameter (temperature) are optimized to reduce strength non-uniformity. The final process design, based on over 360 finite element simulations, meets all material requirements and results in a near uniform strength part.

Keywords: forging; materials properties; parallel processing; finite element analysis; optimal systems

Reprinted with permission from Michael L. Chiesa et al., Parallel Optimization of Forging Processes for Optimal Material Properties, in Conference Proceeding 712, pp. 2080--2084 (2004). Copyright 2004, American Institute of Physics. This article may be downloaded for personal use only. Any other use requires prior permission of the author and the American Institute of Physics.

BibTeX:
@inproceedings{ChJoPeKo04,  
author = {Michael L. Chiesa and Reese E. Jones and Kenneth J. Perano and Tamara G. Kolda}, 
title = {Parallel Optimization of Forging Processes for Optimal Material Properties}, 
booktitle = {NUMIFORM 2004: Proceedings of the 8th International Conference on Numerical Methods in Industrial Forming Processes},
venue = {Columbus, Ohio},
eventdate = {2004-06-13/2004-06-17}, 
series = {AIP Conference Proceedings}, 
volume = {712}, 
pages = {2080-2084}, 
year = {2004},
doi = {10.1063/1.1766841},
}

BibTeX:
@article{SIAM-News-June-2004,  
author = {Tamara G. Kolda}, 
title = {On the Threshold of a New Era for Parallel Computing}, 
journal = {SIAM News}, 
volume = {37}, 
number = {5}, 
month = {June}, 
year = {2004},	
url = {http://www.siam.org/siamnews/06-04/parallel.htm},
}

Abstract: In this paper we prove global convergence for asynchronous parallel pattern search. In standard pattern search, decisions regarding the update of the iterate and the step-length control parameter are synchronized implicitly across all search directions. We lose this feature in asynchronous parallel pattern search since the search along each direction proceeds semiautonomously. By bounding the value of the step-length control parameter after any step that produces decrease along a single search direction, we can prove that all the processes share a common accumulation point and, if the function is continuously differentiable, that such a point is a stationary point of the standard nonlinear unconstrained optimization problem.

Keywords: asynchronous parallel optimization, pattern search, unconstrained optimization, global convergence analysis

© 2004 Society for Industrial and Applied Mathematics

BibTeX:
@article{KoTo04,  
author = {Tamara G. Kolda and Virginia Torczon}, 
title = {On the Convergence of Asynchronous Parallel Pattern Search}, 
journal = {SIAM Journal on Optimization}, 
volume = {14}, 
number = {4}, 
pages = {939--964}, 
month = {May}, 
year = {2004},
doi = {10.1137/S1052623401398107},
}

BibTeX:
@techreport{SAND2004-8055,  
author = {Tamara G. Kolda}, 
title = {Revisiting Asynchronous Parallel Pattern Search for Nonlinear Optimization}, 
number = {SAND2004-8055}, 
institution = {Sandia National Laboratories}, 
month = {February}, 
year = {2004},
}

BibTeX:
@techreport{SAND2003-8550,  
author = {Tamara G. Kolda and Robert Michael Lewis and Virginia Torczon}, 
title = {Stationarity Results for Generating Set Search for Linearly Constrained Optimization}, 
number = {SAND2003-8550}, 
institution = {Sandia National Laboratories}, 
month = {October}, 
year = {2003},
doi = {10.2172/918255},	
url = {http://www.osti.gov/scitech/biblio/918255},
urldate = {2014-04-17},
}

BibTeX:
@techreport{SAND2003-8516,  
author = {Genetha Anne Gray and Tamara G. Kolda and Kenneth L. Sale and Malin M. Young}, 
title = {Optimizing an Empirical Scoring Function for Transmembrane Protein Structure Determination}, 
number = {SAND2003-8516}, 
institution = {Sandia National Laboratories}, 
month = {September}, 
year = {2003},
doi = {10.2172/918349},	
url = {http://www.osti.gov/scitech/biblio/918349},
urldate = {2014-04-17},
}

Abstract: Direct search methods are best known as unconstrained optimization techniques that do not explicitly use derivatives. Direct search methods were formally proposed and widely applied in the 1960s but fell out of favor with the mathematical optimization community by the early 1970s because they lacked coherent mathematical analysis. Nonetheless, users remained loyal to these methods, most of which were easy to program, some of which were reliable. In the past fifteen years, these methods have seen a revival due, in part, to the appearance of mathematical analysis, as well as to interest in parallel and distributed computing.

This review begins by briefly summarizing the history of direct search methods and considering the special properties of problems for which they are well suited. Our focus then turns to a broad class of methods for which we provide a unifying framework that lends itself to a variety of convergence results. The underlying principles allow generalization to handle bound constraints and linear constraints. We also discuss extensions to problems with nonlinear constraints.

Keywords: nonlinear programming, nonlinear optimization, direct search, pattern search, simplex search, positive bases, global convergence analysis, local convergence analysis, generating set search

© 2003 Society for Industrial and Applied Mathematics

BibTeX:
@article{KoLeTo03,  
author = {Tamara G. Kolda and Robert Michael Lewis and Virginia Torczon}, 
title = {Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods}, 
journal = {SIAM Review}, 
volume = {45}, 
number = {3}, 
pages = {385--482}, 
month = {August}, 
year = {2003},
doi = {10.1137/S003614450242889},
}

BibTeX:
@techreport{SAND2003-2927,  
author = {Michael Heroux and Roscoe Bartlett and Vicki Howle and Robert Hoekstra and Jonathan Hu 
and Tamara Kolda and Richard Lehoucq and Kevin Long and Roger Pawlowski 
and Eric Phipps and Andrew Salinger and Heidi Thornquist and Ray Tuminaro 
and James Willenbring and Alan Williams}, 
title = {An overview of {T}rilinos}, 
number = {SAND2003-2927}, 
institution = {Sandia National Laboratories}, 
month = {August}, 
year = {2003},
doi = {10.2172/918383},	
url = {http://www.osti.gov/scitech/biblio/918383},
urldate = {2014-04-17},
}

Abstract: Earlier work has shown that no extension of the Eckart--Young SVD approximation theorem can be made to the strong orthogonal rank tensor decomposition. Here, we present a counterexample to the extension of the Eckart--Young SVD approximation theorem to the orthogonal rank tensor decomposition, answering an open question previously posed by Kolda [SIAM J. Matrix Anal. Appl., 23 (2001), pp. 243--355].

Keywords: singular value decomposition, principal components analysis, multidimensional arrays, higher-order tensor, multilinear algebra

© 2003 Society for Industrial and Applied Mathematics

BibTeX:
@article{Ko03,  
author = {Tamara G. Kolda}, 
title = {A Counterexample to the Possibility of an Extension of the {Eckart-Young} Low-rank Approximation Theorem for the Orthogonal Rank Tensor Decomposition}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {24}, 
number = {3}, 
pages = {762--767}, 
month = {January}, 
year = {2003},
doi = {10.1137/S0895479801394465},
}

Abstract: Asynchronous parallel pattern search (APPS) is a nonlinear optimization algorithm that dynamically initiates actions in response to events, rather than cycling through a fixed set of search directions, as is the case for synchronous pattern search. This gives us a versatile concurrent strategy that allows us to effectively balance the computational load across all available processors. However, the semi-autonomous nature of the search complicates the analysis. We concentrate on elucidating the concepts and notation required to track the iterates produced by APPS across all participating processes. To do so, we consider APPS and its synchronous counterpart (PPS) applied to a simple problem. This allows us both to introduce the bookkeeping we found necessary for the analysis and to highlight some of the fundamental differences between APPS and PPS.

Keywords: nonlinear optimization, asynchronous parallel optimization, pattern search, global convergence, distributed computing, cluster computing

BibTeX:
@incollection{KoTo03,  
author = {Tamara G. Kolda and Virginia Torczon}, 
title = {Understanding Asynchronous Parallel Pattern Search}, 
booktitle = {High Performance Algorithms and Software for Nonlinear Optimization}, 
editor = {G. Di Pillo and A. Murli}, 
series = {Appiled Optimization}, 
volume = {82}, 
publisher = {Springer US}, 
pages = {323-342}, 
year = {2003},
doi = {10.1007/978-1-4613-0241-4_15},
}

BibTeX:
@techreport{SAND2001-8696,  
author = {Tamara G. Kolda and Virginia Torczon}, 
title = {On the Convergence of Asynchronous Parallel Pattern Search}, 
number = {SAND2001-8696}, 
institution = {Sandia National Laboratories}, 
month = {February}, 
year = {2002},
}

Abstract: In this talk we present a Hidden Markov Markov for automatic karyotyping. Previously, we demonstrated that this method is robust in the presence of different types of metaphase spreads, truncation of chromosomes, and minor chromosome abnormalities, and that it gives results superior to neural network on standard data sets. In this work we evaluate it on a data set consisting of a mix of chromosomes obtained from blood, amniotic fluid and bone marrow specimens. The method is shown to be robust on this mixed set of data as well as giving far superior results than that obtained by neural networks.

BibTeX:
@inproceedings{CoBeLeCh01,  
author = {J. M. Conroy and R. L. Becker, Jr. and W. Lefkowitz and K. L. Christopher and R. B. Surana and T. O'Leary and D. P. O'Leary and T. G. Kolda}, 
title = {Hidden {Markov} Models for Chromosome Identification}, 
booktitle = {CBMS 2001: Proceedings of the 14th IEEE Symposium on Computer-Based Medical Systems},
venue = {Bethesda, MD},
eventdate = {2001-07-26/2001-07-27}, 
year = {2001},
doi = {10.1109/CBMS.2001.941764},
}

Abstract: We explore the orthogonal decomposition of tensors (also known as multidimensional arrays or n-way arrays) using two different definitions of orthogonality. We present numerous examples to illustrate the difficulties in understanding such decompositions. We conclude with a counterexample to a tensor extension of the Eckart--Young SVD approximation theorem by Leibovici and Sabatier [Linear Algebra Appl., 269 (1998), pp. 307--329].

Keywords: tensor decomposition, singular value decomposition, principal components analysis, multidimensional arrays

© 2001 Society for Industrial and Applied Mathematics

BibTeX:
@article{Ko01,  
author = {Tamara G. Kolda}, 
title = {Orthogonal Tensor Decompositions}, 
journal = {SIAM Journal on Matrix Analysis and Applications}, 
volume = {23}, 
number = {1}, 
pages = {243--255}, 
month = {July}, 
year = {2001},
doi = {10.1137/S0895479800368354},
}

Abstract: We introduce a new asynchronous parallel pattern search (APPS). Parallel pattern search can be quite useful for engineering optimization problems characterized by a small number of variables (say, fifty or less) and by objective functions that are expensive to evaluate, such as those defined by complex simulations that can take anywhere from a few seconds to many hours to run. The target platforms for APPS are the loosely coupled parallel systems now widely available. We exploit the algorithmic characteristics of pattern search to design variants that dynamically initiate actions solely in response to messages, rather than routinely cycling through a fixed set of steps. This gives a versatile concurrent strategy that allows us to effectively balance the computational load across all available processors. Further, it allows us to incorporate a high degree of fault tolerance with almost no additional overhead. We demonstrate the effectiveness of a preliminary implementation of APPS on both standard test problems as well as some engineering optimization problems.

Keywords: asynchronous parallel optimization, pattern search, direct search, fault tolerance, distributed computing, cluster computing

© 2001 Society for Industrial and Applied Mathematics

BibTeX:
@article{HoKoTo01,  
author = {Patricia D. Hough and Tamara G. Kolda and Virginia J. Torczon}, 
title = {Asynchronous Parallel Pattern Search for Nonlinear Optimization}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {23}, 
number = {1}, 
pages = {134--156}, 
month = {June}, 
year = {2001},
doi = {10.1137/S1064827599365823},
}

BibTeX:
@techreport{SAND2001-8695,  
author = {Tamara G. Kolda and Virginia Torczon}, 
title = {Understanding Asynchronous Parallel Pattern Search}, 
institution = {Sandia National Laboratories}, 
month = {February}, 
year = {2001},
}

Abstract: The analysis of G-banded chromosomes remains the most important tool available to the clinical cytogeneticist. The analysis is laborious when performed manually, and the utility of automated chromosome identification algorithms has been limited by the fact that classification accuracy of these methods seldom exceeds about 80% in routine practice. In this study, we use four new approaches to automated chromosome identification - singular value decomposition (SVD), principal components analysis (PCA), Fisher discriminant analysis (FDA), and hidden Markov models (HMM) - to classify three well-known chromosome data sets (Philadelphia, Edinburgh, and Copenhagen), comparing these approaches with the use of neural networks (NN). We show that the HMM is a particularly robust approach to identification that attains classification accuracies of up to 97% for normal chromosomes and retains classification accuracies of up to 95% when chromosome telomeres are truncated or small portions of the chromosome are inverted. This represents a substantial improvement of the classification accuracy for normal chromosomes, and a doubling in classification accuracy for truncated chromosomes and those with inversions, as compared with NN-based methods. HMMs thus appear to be a promising approach for the automated identification of both normal and abnormal G-banded chromosomes.

© 2000 The United States and Canadian Academy of Pathology, Inc.

BibTeX:
@article{CoKoOlOl00,  
author = {John M. Conroy and Tamara G. Kolda and Dianne P. O'Leary and Timothy J. O'Leary}, 
title = {Chromosome Identification Using Hidden {Markov} Models: Comparison with Neural Networks, Singular Value Decomposition, Principal Components Analysis, and {Fisher} Discriminant Analysis}, 
journal = {Laboratory Investigation}, 
volume = {80}, 
number = {11}, 
pages = {1629--1641}, 
month = {November}, 
year = {2000},
doi = {10.1038/labinvest.3780173},
}

Abstract: Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.

Keywords: Graph partitioning; hypergraph partitioning; parallel computing

Copyright © Elsevier Science B.V. All rights reserved.

BibTeX:
@article{HeKo00,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Graph Partitioning Models for Parallel Computing}, 
journal = {Parallel Computing}, 
volume = {26}, 
number = {12}, 
pages = {1519--1534}, 
month = {November}, 
year = {2000},
doi = {10.1016/S0167-8191(00)00048-X},
}

Abstract: We present algorithms for computing a semidiscrete approximation to a matrix in a weighted norm, with the Frobenius norm as a special case. The approximation is formed as a weighted sum of outer products of vectors whose elements are +/- 1 or 0, so the storage required by the approximation is quite small. We also present a related algorithm for approximation of a tensor. Applications of the algorithms are presented to data compression, filtering, and information retrieval; software is provided in C and in Matlab.

Keywords: compression, latent semantic indexing, matrix decomposition, semidiscrete decomposition (SDD), singular value decomposition (SVD)

The published version has several typographical errors. You may wish instead to check the older version.

© 2000 ACM.

BibTeX:
@article{KoOl00,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {Algorithm 805: Computation and Uses of the Semidiscrete Matrix Decomposition}, 
journal = {ACM Transactions on Mathematical Software}, 
volume = {26}, 
number = {3}, 
pages = {415--435}, 
month = {September}, 
year = {2000},
doi = {10.1145/358407.358424},
}

Abstract: Usage manual for APPSPACK, an asynchronous parallel pattern search method for optimization.

Keywords: asynchronous parallel optimization, pattern search, direct search, fault tolerance, distirbuted computing, cluster computing

BibTeX:
@techreport{SAND2000-8843,  
author = {P. D. Hough and T. G. Kolda and H. A. Patrick}, 
title = {Usage Manual for {APPSPACK} 2.0}, 
number = {SAND2000-8843}, 
institution = {Sandia National Laboratories}, 
year = {2000},
}

Abstract: A common operation in scientific computing is the multiplication of a sparse, rectangular, or structurally unsymmetric matrix and a vector. In many applications the matrix-transpose-vector product is also required. This paper addresses the efficient parallelization of these operations. We show that the problem can be expressed in terms of partitioning bipartite graphs. We then introduce several algorithms for this partitioning problem and compare their performance on a set of test matrices.

Keywords: matrix partitioning, iterative method, parallel computing, rectangular matrix, structurally unsymmetric matrix, bipartite graph

© 2000 Society for Industrial and Applied Mathematics

BibTeX:
@article{HeKo00a,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Partitioning Rectangular and Structurally Unsymmetric Sparse Matrices for Parallel Processing}, 
journal = {SIAM Journal on Scientific Computing}, 
volume = {21}, 
number = {6}, 
pages = {2048--2072}, 
month = {May}, 
year = {2000},
doi = {10.1137/S1064827598341475},
}

BibTeX:
@techreport{SAND2000-8213,  
author = {Patricia D. Hough and Tamara G. Kolda and Virginia J. Torczon}, 
title = {Asynchronous Parallel Pattern Search for Nonlinear Optimization}, 
volume = {23}, 
number = {SAND2000-8213}, 
institution = {Sandia National Laboratories}, 
pages = {134--156}, 
month = {January}, 
year = {2000},
}

Also available as Institute for Advanced Computer Studies Report UMIACS-TR-99-22, University of Maryland, College Park, Maryland, 1999.

BibTeX:
@techreport{ORNL-TM-13766,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {Computation and Uses of the Semidiscrete Matrix Decomposition}, 
number = {ORNL-TM-13766}, 
institution = {Oak Ridge National Laboratory}, 
month = {April}, 
year = {1999},
}

Abstract: The goal in information retrieval is to enable users to automatically and accurately find data relevant to their queries. One possible approach to this problem is to use the vector space model, which models documents and queries as vectors in the term space. The components of the vectors are determined by the term weighting scheme, a function of the frequencies of the terms in the document or query as well as throughout the collection. We discuss popular term weighting schemes and present several new schemes that offer improved performance.

BibTeX:
@techreport{ORNL-TM-13756,  
author = {Erica Chisholm and Tamara G. Kolda}, 
title = {New Term Weighting Formulas for the Vector Space Method in Information Retrieval}, 
number = {ORNL-TM-13756}, 
institution = {Oak Ridge National Laboratory}, 
month = {March}, 
year = {1999},
}

Abstract: With the electronic storage of documents comes the possibility of building search engines that can automatically choose documents relevant to a given set of topics. In information retrieval, we wish to match queries with relevant documents. Documents can be represented by the terms that appear within them, but literal matching of terms does not necessarily retrieve all relevant documents. There are a number of information retrieval systems based on inexact matches. Latent Semantic Indexing represents documents by approximations and tends to cluster documents on similar topics even if their term profiles are somewhat different. This approximate representation is usually accomplished using a low-rank singular value decomposition (SVD) approximation. In this paper, we use an alternate decomposition, the semi-discrete decomposition (SDD). For equal query times, the SDD does as well as the SVD and uses less than one-tenth the storage for the MEDLINE test set.

PDF and postscript files are preprints from January 1997.

BibTeX:
@incollection{KoOl99,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {Latent Semantic Indexing Via a Semi-discrete Matrix Decomposition}, 
booktitle = {The Mathematics of Information Coding, Extraction and Distribution}, 
editor = {G. Cybenko and Dianne P. O'Leary and Jorma Rissanen}, 
series = {IMA Volumes in Mathematics and Its Applications}, 
volume = {107}, 
publisher = {Springer New York}, 
pages = {73--80}, 
year = {1999},
doi = {10.1007/978-1-4612-1524-0_5},
}

Abstract: We give conditions under which limited-memory quasi-Newton methods with exact line searches will terminate in n steps when minimizing n-dimensional quadratic functions. We show that although all Broyden family methods terminate in n steps in their full-memory versions, only BFGS does so with limited-memory. Additionally, we show that full-memory Broyden family methods with exact line searches terminate in at most n + p steps when p matrix updates are skipped. We introduce new limited-memory BFGS variants and test them on nonquadratic minimization problems.

Keywords: minimization, quasi-Newton, BFGS, limited-memory, update skipping, Broyden family

The companion web page (with source code) is http://www.cs.umd.edu/~oleary/LBFGS/.

© 1998 Society for Industrial and Applied Mathematics

BibTeX:
@article{KoOlNa98,  
author = {Tamara G. Kolda and Dianne P. O'Leary and Larry Nazareth}, 
title = {{BFGS} with Update Skipping and Varying Memory}, 
journal = {SIAM Journal on Optimization}, 
volume = {8}, 
number = {4}, 
pages = {1060--1083}, 
month = {November}, 
year = {1998},
doi = {10.1137/S1052623496306450},
}

Abstract: The vast amount of textual information available today is useless unless it can be effectively and efficiently searched. The goal in information retrieval is to find documents that are relevant to a given user query. We can represent and document collection by a matrix whose (i, j) entry is nonzero only if the ith term appears in the jth document; thus each document corresponds to a columm vector. The query is also represented as a column vector whose ith term is nonzero only if the ith term appears in the query. We score each document for relevancy by taking its inner product with the query. The highest-scoring documents are considered the most relevant. Unfortunately, this method does not necessarily retrieve all relevant documents because it is based on literal term matching. Latent semantic indexing (LSI) replaces the document matrix with an approximation generated by the truncated singular-value decomposition (SVD). This method has been shown to overcome many difficulties associated with literal term matching. In this article we propose replacing the SVD with the semidiscrete decomposition (SDD). We will describe the SDD approximation, show how to compute it, and compare the SDD-based LSI method to the SVD-based LSI methods. We will show that SDD-based LSI does as well as SVD-based LSI in terms of document retrieval while requiring only one-twentieth the storage and one-half the time to compute each query. We will also show how to update the SDD approximation when documents are added or deleted from the document collection.

Keywords: data mining, latent semantic indexing, semidiscrete decomposition, singular-value decomposition, text retrieval

Review from Computing Reviews.

© 1998 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Information Systems (TOIS), Volume 16, Issue 4 (October 1998), http://doi.acm.org/10.1145/291128.291131.

BibTeX:
@article{KoOl98,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {A Semidiscrete Matrix Decomposition for Latent Semantic Indexing Information Retrieval}, 
journal = {ACM Transactions on Information Systems}, 
volume = {16}, 
number = {4}, 
pages = {322--346}, 
month = {October}, 
year = {1998},
doi = {10.1145/291128.291131},
}

BibTeX:
@techreport{ORNL-TM-13657,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Graph Partitioning Models for Parallel Computing}, 
number = {ORNL-TM-13657}, 
institution = {Oak Ridge National Laboratory}, 
month = {September}, 
year = {1998},
}

Abstract: We are interested in partitioning sparse rectangular matrices for parallel processing. The partitioning problem has been well-studied in the square symmetric case, but the rectangular problem has received very little attention. We will formalize the rectangular matrix partitioning problem and discuss several methods for solving it. We will extend the spectral partitioning method for symmetric matrices to the rectangular case and compare this method to three new methods --- the alternating partitioning method and two hybrid methods. The hybrid methods will be shown to be best.

PDF and postscript files are preprints.

BibTeX:
@inproceedings{Ko98,  
author = {Tamara G. Kolda}, 
title = {Partitioning Sparse Rectangular Matrices for Parallel Processing}, 
booktitle = {Solving Irregularly Structured Problems in Parallel}, 
eventtitle = {5th International Symposium, IRREGULAR'98},
venue = {Berkeley, CA},
eventdate = {1998-08-09/1998-08-11}, 
editor = {A. Ferreira and others}, 
series = {Lecture Notes in Computer Science}, 
volume = {1457}, 
number = {1457}, 
publisher = {Springer Berlin Heidelberg}, 
pages = {68-79}, 
year = {1998},
doi = {10.1007/BFb0018528},
}

Abstract: This paper addresses the problem of partitioning the nonzeros of sparse nonsymmetric and nonsquare matrices in order to efficiently compute parallel matrix-vector and matrix-transpose-vector multiplies. Our goal is to balance the work per processor while keeping communications costs low. Although the symmetric partitioning problem has been well-studied, the nonsymmetric and rectangular cases have received scant attention. We show that this problem can be described as a partitioning problem on a bipartite graph. We then describe how to use (modified) multilevel methods to partition these graphs and how to implement the matrix multiplies in parallel to take advantage of the partitioning. Finally, we compare various multilevel and other partitioning strategies on matrices from different applications. The multilevel methods are shown to be best.

PDF and postscript files are preprints.

BibTeX:
@inproceedings{HeKo98,  
author = {Bruce Hendrickson and Tamara G. Kolda}, 
title = {Partitioning Sparse Rectangular Matrices for Parallel Computations of $Ax$ and $A^Tv$}, 
booktitle = {Applied Parallel Computing Large Scale Scientific and Industrial Problems}, 
eventtitle = {4th International Workshop, PARA'98},
venue = {Ume\r{a}, Sweden},
eventdate = {1998-06-14/1998-06-17}, 
editor = {B. K\r{a}gstr\"{o}m and others}, 
series = {Lecture Notes in Computer Science}, 
volume = {1541}, 
number = {1541}, 
publisher = {Springer Berlin Heidelberg}, 
pages = {239-247}, 
year = {1998},
doi = {10.1007/BFb0095342},
}

Abstract: The focus of this dissertation is on matrix decompositions that use a limited amount of computer memory, thereby allowing problems with a very large number
of variables to be solved. Specifically, we will focus on two applications areas: optimization and information retrieval.

We introduce a general algebraic form for the matrix update in limited-memory quasi-Newton methods. Many well-known methods such as limited-memory Broyden Family methods satisfy the general form. We are able to prove several results about methods which satisfy the general form. In particular, we show that the only limited-memory Broyden Family method (using exact line searches) that is guaranteed to terminate within n iterations on an n-dimensional strictly convex quadratic is the limited-memory BFGS method. Furthermore, we are able to introduce several new variations on the limited-memory BFGS method that retain the quadratic termination property. We also have a new result that shows that full-memory Broyden Family methods (using exact line searches) that skip p updates to the quasi-Newton matrix will terminate in no more than n+p steps on an n-dimensional strictly convex quadratic. We propose several new variations on the limited-memory BFGS method and test these on standard test problems.

We also introduce and test a new method for a process known as Latent Semantic Indexing (LSI) for information retrieval. The new method replaces the singular value matrix decomposition (SVD) at the heart of LSI with a semi-discrete matrix decomposition (SDD). We show several convergence results for the SDD and compare some strategies for computing it on general matrices. We also compare the SVD-based LSI to the SDD-based LSI and show that the SDD-based method has a faster query computation time and requires significantly less storage. We also propose and test several SDD-updating strategies for adding new documents to the collection.

Also available as Technical Report UMCP-CS-TR-3806, Department of Computer Science, University of Maryland, College Park, MD, April 1997.

BibTeX:
@phdthesis{UMCP-CS-TR-3806,  
author = {Tamara G. Kolda}, 
title = {Limited-Memory Matrix Methods with Applications}, 
school = {Applied Mathematics Program, University of Maryland, College Park}, 
year = {1997},
}

BibTeX:
@techreport{UMCP-CS-TR-3724,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {A Semidiscrete Matrix Decomposition for Latent Semantic Indexing Information Retrieval}, 
number = {UMCP-CS-TR-3724}, 
institution = {University of Maryland Department of Computer Science, College Park, MD}, 
month = {December}, 
year = {1996},
}

BibTeX:
@techreport{UMCP-CS-TR-3713,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {Latent Semantic Indexing via a Semi-discrete Matrix Decomposition}, 
number = {UMCP-CS-TR-3713}, 
institution = {University of Maryland Department of Computer Science, College Park, MD}, 
month = {November}, 
year = {1996},
}

BibTeX:
@techreport{UMCP-CS-TR-3663,  
author = {Tamara G. Kolda and Dianne P. O'Leary and Larry Nazareth}, 
title = {{BFGS} with Update Skipping and Varying Memory}, 
number = {UMCP-CS-TR-3663}, 
institution = {University of Maryland Department of Computer Science, College Park, MD}, 
month = {July}, 
year = {1996},
}

BibTeX:
@techreport{CRSC-TR96-7,  
author = {Tamara L. {Gibson (nee Kolda)} and Jennifer Hill and Christina Juergens and Sridar Pootheri and Laura Potter and Shirley Stolarski}, 
title = {Matching Permuted Variables in Two or More Data Sets}, 
number = {CRSC-TR96-7}, 
institution = {Center for Research in Scientific Computation, North Carolina State University}, 
year = {1996},
}

Abstract: The NAS Parallel Benchmark kernels were developed to evaluate the performance of highly-parallel supercomputers. These benchmarks are unstructured in the sense that they give only an algorithm defining the benchmark; all implementation details are left to the programmer. We looked specifically at a kernel to solve an unstructured sparse linear system via the conjugate gradient method, the CG kernel. This kernel was implemented on one of the newest massively-parallel supercomputers, the Cray T3D. Currently, our implementation of the CG kernel on the T3D achieves 306 MFlops on 64 processors. In comparison, a Cray YMP single head gets 127 MFlops, a 128 processor iPSC/860 gets 181 MFlops, and a 32,768 processor CM-2 gets 105 MFlops.

BibTeX:
@techreport{SRC-TR-94-192,  
author = {Tamara L. {Gibson (nee Kolda)}}, 
title = {The {NAS} Parallel Conjugate Gradient Benchmark on the {Cray} {T3D}}, 
number = {SRC-TR-94-192}, 
institution = {Supercomputing Research Center, Bowie, MD}, 
year = {1994},
}

Created by JabRef on 18/12/2014.