Virginia Tech - Wake Forest University School of Biomedical Engineering & Sciences
Computer Science Technical Reports @Virginia TechNot a member yet
997 research outputs found
Sort by
Performance Modeling and Analysis of a Massively Parallel DIRECT— Part 1
Get PDFModeling and analysis techniques are used to investigate
the performance of a massively parallel version
of DIRECT, a global search algorithm widely used
in multidisciplinary design optimization applications.
Several highdimensional
benchmark functions and
real world problems are used to test the design effectiveness
under various problem structures. Theoretical
and experimental results are compared for two
parallel clusters with different system scale and network
connectivity. The present work aims at studying
the performance sensitivity to important parameters
for problem configurations, parallel schemes,
and system settings. The performance metrics
include the memory usage, load balancing, parallel
efficiency, and scalability. An analytical bounding
model is constructed to measure the load balancing
performance under different schemes. Additionally,
linear regression models are used to characterize
two major overhead sources—interprocessor communication
and processor idleness, and also applied
to the isoefficiency functions in scalability analysis.
For a variety of highdimensional
problems and large
scale systems, the massively parallel design has
achieved reasonable performance. The results of
the performance study provide guidance for efficient
problem and scheme configuration. More importantly,
the generalized design considerations and
analysis techniques are beneficial for transforming
many global search algorithms to become effective
large scale parallel optimization tools
Parallel scalability study of three dimensional additive Schwarz preconditioners in non-overlapping domain decomposition
Get PDFIn this paper we study the parallel scalability of variants of additive Schwarz preconditioners for three dimensional non-overlapping domain decomposition methods. To alleviate the
computational cost, both in terms of memory and floating-point complexity, we investigate
variants based on a sparse approximation or on mixed 32- and 64-bit calculation. The robustness of the preconditioners is illustrated on a set of linear systems arising from the finite
element discretization of elliptic PDEs through extensive parallel experiments on up to 1000
processors. Their efficiency from a numerical and parallel performance view point are studied
Performance Evaluation of Navigation Approaches on High-resolution Displays
Get PDFWe conducted a study to discover if the data navigation techniques suitable for high-resolution displays differed significantly from those traditionally used for single-screen desktop displays. The high-resolution capability of the former display makes it possible to show more data at once without having the user drill-down to get to the details. At the same time, the larger physical size makes it difficult for the user to interact with such a display using current day interaction techniques. Given these factors, we compare the performance of users on tasks that involve navigating into hierarchically-structured data. The specific visualization we use is a cushion treemap, displayed at multiple resolutions—on a 3x3, 17†tiled screen display; on a 2x2, 17†tiled screen display; on a single 17†screen display, and on a 66†SMART Board™. Through the performance evaluation of 24 users, we show that beyond a certain resolution and physical screen size, the drill-down technique fares relatively poorly, while the straightforward technique of displaying all the data at once results in better performance at the tasks we studied
A Polynomial Chaos Based Bayesian Approach for Estimating Uncertain Parameters of Mechanical Systems – Part I: Theoretical Approach
Get PDFThis is the first part of a two-part article. A new computational approach for parameter estimation is proposed based on the application of the polynomial chaos theory. The polynomial chaos method has been shown to be considerably more efficient than Monte Carlo in the simulation of systems with a small number of uncertain parameters. In the new approach presented in this paper, the maximum likelihood estimates are obtained by minimizing a cost function derived from the Bayesian theorem. Direct stochastic collocation is used as a less computationally expensive alternative to the traditional Galerkin approach to propagate the uncertainties through the system in the polynomial chaos framework. This approach is applied to very simple mechanical systems in order to illustrate how the cost function can be affected by undersampling, non-identifiablily of the system, non-observability, and by excitation signals that are not rich enough. When the system is non-identifiable, regularization techniques can still yield most likely values among the possible combinations of uncertain parameters resulting in the same time responses than the ones observed. This is illustrated using a simple spring-mass system. Possible applications of this theory to the field of vehicle dynamics simulations include the estimation of mass, inertia properties, as well as other parameters of interest. In the second part of this article, this new parameter estimation method is illustrated on a nonlinear four-degree-of-freedom roll plane model of a vehicle in which an uncertain mass with an uncertain position is added on the roll bar
Reduced Sampling for Construction of Quadratic Response Surface Approximations Using Adaptive Experimental Design
Get PDFThe purpose of this paper is to reduce the computational complexity per step from O(n^2) to O(n) for optimization based on quadratic surrogates, where n is the number of design variables. Applying nonlinear optimization strategies directly to complex
multidisciplinary systems can be prohibitively expensive when the complexity of the simulation codes is large. Increasingly, response surface approximations, and specifically quadratic approximations, are being integrated with nonlinear optimizers in order to reduce the CPU time required for the optimization of complex multidisciplinary systems. For evaluation by the optimizer, response surface approximations provide a computationally inexpensive lower fidelity representation of the system performance. The curse of dimensionality is a major drawback in the implementation of these approximations as the amount of required data grows quadratically with the number n of design variables in the problem. In this paper a novel technique to reduce the magnitude of the sampling from O(n^2) to O(n) is presented. The technique uses prior information to approximate the eigenvectors of the Hessian matrix of the response surface approximation and only requires the eigenvalues to be computed by response surface techniques. The technique is implemented in a sequential approximate optimization algorithm and applied to engineering problems of variable size and characteristics. Results demonstrate that a reduction in the data required per step from O(n^2) to O(n) points can be accomplished without significantly compromising the performance of the optimization algorithm. A reduction in the time (number of system analyses) required per step from O(n^2) to O(n) is significant, even more so as n increases. The novelty lies in how only O(n) system analyses can be used to approximate a Hessian matrix whose estimation normally requires O(n^2) system analyses
Feature Reduction using a Singular Value Decomposition for the Iterative Guided Spectral Class Rejection Hybrid Classifier
Get PDFFeature reduction in a remote sensing dataset is often desirable to decrease the processing
time required to perform a classification and improve overall classification accuracy. This work introduces
a feature reduction method based on the singular value decomposition (SVD). This feature reduction
technique was applied to training data from two multitemporal datasets of Landsat TM/ETM+ imagery
acquired over a forested area in Virginia, USA and Rondonia, Brazil. Subsequent parallel iterative guided
spectral class rejection (pIGSCR) forest/nonforest
classifications were performed to determine the quality
of the feature reduction. The classifications of the Virginia data were five times faster using SVDbased
feature reduction without affecting the classification accuracy. Feature reduction using the SVD was also
compared to feature reduction using principal components analysis (PCA). The highest average accuracies
for the Virginia dataset (88.34%) and for the Rondonia dataset (93.31%) were achieved using the SVD.
The results presented here indicate that SVDbased
feature reduction can produce statistically significantly
better classifications than PCA
Efficient Uncertainty Quantification with the Polynomial Chaos Method for Stiff Systems
Get PDFThe polynomial chaos method has been widely adopted as a computationally
feasible approach for uncertainty quantification. Most studies to date
have focused on non-stiff systems. When stiff systems are considered,
implicit numerical integration requires the solution of a nonlinear
system of equations at every time step. Using the Galerkin approach, the
size of the system state increases from to , where
is the number of the polynomial chaos basis functions. Solving such systems with full
linear algebra causes the computational cost to increase from to
. The -fold increase can make the computational cost
prohibitive. This paper explores computationally efficient uncertainty
quantification techniques for stiff systems using the Galerkin, collocation and collocation least-squares formulations of polynomial chaos. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the
Jacobian matrix to reduce the computational cost. The numerical results
show a run time reduction with a small impact on accuracy. In
the stochastic collocation formulation, we propose a least-squares
approach based on collocation at a low-discrepancy set of
points. Numerical experiments illustrate that the collocation
least-squares approach for uncertainty quantification has similar
accuracy with the Galerkin approach, is more efficient, and does not
require any modifications of the original code
Modeling Multigrain Parallelism on Heterogeneous Multi-core Processors
Get PDFHeterogeneous multi-core processors integrate conventional processing
cores with computational accelerators. To maximize performance on
these systems, programs must exploit multiple dimensions of
parallelism simultaneously, including task-level and data-level
parallelism. Unfortunately, parallel program designs with multiple
dimensions of parallelism today are ad hoc, resulting in performance
that depends heavily on the intuition and skill of the
programmer. Formal techniques are needed to optimize parallel program
designs. We propose a parallel computational model for steering
multi-grain parallelization in heterogeneous multi-core
processors. Our model accurately predicts the execution time and
scalability of a program using multiple conventional processors and
accelerators. The model reveals optimal degrees of multi-dimensional,
task-level and data-level concurrency in parallel programs. We use the
model to derive mappings of two full computational phylogenetics
applications on multi-processors featuring the IBM Cell Broadband
Engine
Discrete Second Order Adjoints in Atmospheric Chemical Transport Modeling
Get PDFAtmospheric chemical transport models (CTMs) are essential tools for the study of air pollution, for environmental policy decisions, for the interpretation of observational data, and for producing air quality forecasts. Many air quality studies require sensitivity analyses, i.e., the computation of derivatives of the model output with respect to model parameters. The derivatives of a cost functional (defined on the model output) with respect to a large number of model parameters can be calculated efficiently through adjoint sensitivity analysis. While the traditional (first order) adjoint models give the gradient of the cost functional with respect to parameters, second order adjoint models give second derivative information in the form of products between the Hessian of the cost functional and a user defined vector.
In this paper we discuss the mathematical foundations of the discrete second order adjoint sensitivity method and present a complete set of computational tools for performing second order sensitivity studies in three-dimensional atmospheric CTMs. The tools include discrete second order adjoints of Runge Kutta and of Rosenbrock time stepping methods for stiff equations together with efficient implementation strategies. Numerical examples illustrate the use of these computational tools in important applications like sensitivity analysis, optimization, uncertainty quantification, and the calculation of directions of maximal error growth in three-dimensional atmospheric CTMs
Mining Novellas from PubMed Abstracts using a Storytelling Algorithm
Get PDFMotivation: There are now a multitude of articles published in a diversity of journals providing information about genes, proteins, pathways, and entire processes. Each article investigates particular subsets of a biological process, but to gain insight into the functioning of a system as a whole, we must computationally integrate information across multiple publications. This is especially important in problems such as modeling cross-talk in signaling networks, designing drug therapies for combinatorial selectivity, and unraveling the role of gene interactions in deleterious phenotypes, where the cost of performing combinatorial screens is exorbitant.
Results: We present an automated approach to biological knowledge discovery from PubMed abstracts, suitable for unraveling combinatorial relationships. It involves the systematic application of a `storytelling' algorithm followed by compression of the stories into `novellas.' Given a start and end publication, typically with little or no overlap in content, storytelling identifies a chain of intermediate publications from one to the other, such that neighboring publications have significant content similarity. Stories discovered thus provide an argued approach to relate distant concepts through compositions of related concepts. The chains of links employed by stories are then mined to find frequently reused sub-stories, which can be compressed to yield novellas, or compact templates of connections. We demonstrate a successful application of storytelling and novella finding to modeling combinatorial relationships between introduction of extracellular factors and downstream cellular events.
Availability: A story visualizer, suitable for interactive exploration of stories and novellas described in this paper, is available for demo/download at https://bioinformatics.cs.vt.edu/storytelling