In ACM TOMS Algorithm 1012, the DELAUNAYSPARSE software is given for performing Delaunay interpolation in medium to high dimensions. When extrapolating outside the convex hull of the training set, DELAUNAYSPARSE calls the nonnegative least squares solver DWNNLS to compute projections onto the convex hull. However, DWNNLS and many other available sum-of-squares optimization solvers were not intended for usage with many variable problems, which result from the large training sets that are typical in machine learning applications. Thus, a new PROJECT subroutine is given, based on the highly customizable quadratic program solver BQPD . This solution is shown to be as robust as DELAUNAYSPARSE for projection onto both synthetic and real-world datasets, where other available solvers frequently fail. Although it is intended as an update for DELAUNAYSPARSE , due to the difficulty and prevalence of the problem, this solution is likely to be of external interest as well.

MOTIVATION: The human microbiome, which is linked to various diseases by growing evidence, has a profound impact on human health. Since changes in the composition of the microbiome across time are associated with disease and clinical outcomes, microbiome analysis should be performed in a longitudinal study. However, due to limited sample sizes and differing numbers of timepoints for different subjects, a significant amount of data cannot be utilized, directly affecting the quality of analysis results. Deep generative models have been proposed to address this lack of data issue. Specifically, a generative adversarial network (GAN) has been successfully utilized for data augmentation to improve prediction tasks. Recent studies have also shown improved performance of GAN-based models for missing value imputation in a multivariate time series dataset compared with traditional imputation methods. RESULTS: This work proposes DeepMicroGen, a bidirectional recurrent neural network-based GAN model, trained on the temporal relationship between the observations, to impute the missing microbiome samples in longitudinal studies. DeepMicroGen outperforms standard baseline imputation methods, showing the lowest mean absolute error for both simulated and real datasets. Finally, the proposed model improved the predicted clinical outcome for allergies, by providing imputation for an incomplete longitudinal dataset used to train the classifier. AVAILABILITY AND IMPLEMENTATION: DeepMicroGen is publicly available at https://github.com/joungmin-choi/DeepMicroGen.

MQSI is a Fortran 2003 subroutine for constructing monotone quintic spline interpolants to univariate monotone data. Using sharp theoretical monotonicity constraints, first and second derivative estimates at data provided by a quadratic facet model are refined to produce a univariate C 2 monotone interpolant. Algorithm and implementation details, complexity and sensitivity analyses, usage information, a brief performance study, and comparisons with other spline approaches are included.

The cell cycle of Caulobacter crescentus involves the polar morphogenesis and an asymmetric cell division driven by precise interactions and regulations of proteins, which makes Caulobacter an ideal model organism for investigating bacterial cell development and differentiation. The abundance of molecular data accumulated on Caulobacter motivates system biologists to analyze the complex regulatory network of cell cycle via quantitative modeling. In this paper, We propose a comprehensive model to accurately characterize the underlying mechanisms of cell cycle regulation based on the study of: a) chromosome replication and methylation; b) interactive pathways of five master regulatory proteins including DnaA, GcrA, CcrM, CtrA, and SciP, as well as novel consideration of their corresponding mRNAs; c) cell cycle-dependent proteolysis of CtrA through hierarchical protease complexes. The temporal dynamics of our simulation results are able to closely replicate an extensive set of experimental observations and capture the main phenotype of seven mutant strains of Caulobacter crescentus. Collectively, the proposed model can be used to predict phenotypes of other mutant cases, especially for nonviable strains which are hard to cultivate and observe. Moreover, the module of cyclic proteolysis is an efficient tool to study the metabolism of proteins with similar mechanisms.

Remote exploitation attacks use software vulnerabilities to penetrate through a network of Internet of Things (IoT) devices. This work addresses defending against remote exploitation attacks on vulnerable IoT devices. As an attack mitigation strategy, we assume it is not possible to fix all the vulnerabilities and propose to diversify the open-source software used to manage IoT devices. Our approach is to deploy dynamic cloud-based virtual machine proxies for physical IoT devices. Our architecture leverages virtual machine proxies with diverse software configurations to mitigate vulnerable and static software configurations on physical devices. We develop an algorithm for selecting new configurations based on network anomaly detection signals to learn vulnerable software configurations on IoT devices, automatically shifting towards more secure configurations. Cloud-based proxy machines mediate requests between application clients and vulnerable IoT devices, facilitating a dynamic diversification system. We report on simulation experiments to evaluate the dynamic system. Two models of powerful adversaries are introduced and simulated against the diversified defense strategy. Our experiments show that a dynamically diversified IoT architecture can be invulnerable to large classes of attacks that would succeed against a static architecture.

VTMOP is a Fortran 2008 software package containing two Fortran modules for solving computationally expensive bound-constrained blackbox multiobjective optimization problems. VTMOP implements the algorithm of [ 32 ], which handles two or more objectives, does not require any derivatives, and produces well-distributed points over the Pareto front. The first module contains a general framework for solving multiobjective optimization problems by combining response surface methodology, trust region methodology, and an adaptive weighting scheme. The second module features a driver subroutine that implements this framework when the objective functions can be wrapped as a Fortran subroutine. Support is provided for both serial and parallel execution paradigms, and VTMOP is demonstrated on several test problems as well as one real-world problem in the area of particle accelerator optimization.

One way to combat denial-of-service attacks on cloud-based virtual networks is to use unpredictable network addresses, aiming to increase attacker effort by requiring attackers to search a large IP address space to find a target host. IP address randomization is used by several moving target defenses, relying on the assumption that it is difficult for an attacker to predict newly allocated IP addresses. This paper analyzes whether IP addresses used by cloud providers are unpredictable enough in practice. We analyze the IP address allocation behaviors in two major cloud computing providers (Amazon Web Services and Google Cloud Platform) and find that the actual entropy provided by allocated IP addresses is limited. We evaluate several prediction models, including a simple frequency-based model as well as a Markov process model that produces an address prediction set from time series data of collected IP addresses. Our results show that simple models can reduce the search space for allocated IP addresses and diminish the effectiveness of randomization defenses.

With current IoT architectures, once a single device in a network is compromised, it can be used to disrupt the behavior of other devices on the same network. Even though system administrators can secure critical devices in the network using best practices and state-of-the-art technology, a single vulnerable device can undermine the security of the entire network. The goal of this work is to limit the ability of an attacker to exploit a vulnerable device on an IoT network and fabricate deceitful messages to co-opt other devices. The approach is to limit attackers by using device proxies that are used to retransmit and control network communications. We present an architecture that prevents deceitful messages generated by compromised devices from affecting the rest of the network. The design assumes a centralized and trustworthy machine that can observe the behavior of all devices on the network. The central machine collects application layer data, as opposed to low-level network traffic, from each IoT device. The collected data is used to train models that capture the normal behavior of each individual IoT device. The normal behavioral data is then used to monitor the IoT devices and detect anomalous behavior. This paper reports on our experiments using both a binary classifier and a density-based clustering algorithm to model benign IoT device behavior with a realistic test-bed, designed to capture normal behavior in an IoT-monitored environment. Results from the IoT testbed show that both the classifier and the clustering algorithms are promising and encourage the use of application-level data for detecting compromised IoT devices.

QNSTOP consists of serial and parallel (OpenMP) Fortran 2003 codes for the quasi-Newton stochastic optimization method of Castle and Trosset for stochastic search problems. A complete description of QNSTOP for both local search with stochastic objective and global search with “noisy” deterministic objective is given here, to the best of our knowledge, for the first time. For stochastic search problems, some convergence theory exists for particular algorithmic choices and parameter values. Both the parallel driver subroutine, which offers several parallel decomposition strategies, and the serial driver subroutine can be used for local stochastic search or global deterministic search, based on an input switch. Some performance data for computational systems biology problems is given.

DELAUNAYSPARSE contains both serial and parallel codes written in Fortran 2003 (with OpenMP) for performing medium- to high-dimensional interpolation via the Delaunay triangulation. To accommodate the exponential growth in the size of the Delaunay triangulation in high dimensions, DELAUNAYSPARSE computes only a sparse subset of the complete Delaunay triangulation, as necessary for performing interpolation at the user specified points. This article includes algorithm and implementation details, complexity and sensitivity analyses, usage information, and a brief performance study.

Parameter estimation in discrete or continuous deterministic cell cycle models is challenging for several reasons, including the nature of what can be observed, and the accuracy and quantity of those observations. The challenge is even greater for stochastic models, where the number of simulations and amount of empirical data must be even larger to obtain statistically valid parameter estimates. The two main contributions of this work are (1) stochastic model parameter estimation based on directly matching multivariate probability distributions, and (2) a new quasi-Newton algorithm class QNSTOP for stochastic optimization problems. QNSTOP directly uses the random objective function value samples rather than creating ensemble statistics. QNSTOP is used here to directly match empirical and simulated joint probability distributions rather than matching summary statistics. Results are given for a current state-of-the-art stochastic cell cycle model of budding yeast, whose predictions match well some summary statistics and one-dimensional distributions from empirical data, but do not match well the empirical joint distributions. The nature of the mismatch provides insight into the weakness in the stochastic model.

Exponential increases in complexity and scale make variability a growing threat to sustaining HPC performance at exascale. Performance variability in HPC I/O is common, acute, and formidable. We take the first step towards comprehensively studying linear and nonlinear approaches to modeling HPC I/O system variability in an effort to demonstrate that variability is often a predictable artifact of system design. Using over 8 months of data collection on 6 identical systems, we propose and validate a modeling and analysis approach (MOANA) that predicts HPC I/O variability for thousands of software and hardware configurations on highly parallel shared-memory systems. Our findings indicate nonlinear approaches to I/O variability prediction are an order of magnitude more accurate than linear regression techniques. We demonstrate the use of MOANA to accurately predict the confidence intervals of unmeasured I/O system configurations for a given number of repeat runs - enabling users to quantitatively balance experiment duration with statistical confidence.

When remote command injection attacks succeed at the entry points of a cloud (servers exposed to the outside Internet), attackers targeting a specific asset in the cloud will pursue further exploration to find their targets. Attack targets, such as database servers, are often running on separate machines, forcing an extra step for a successful attack. However, compromising two or three machines is all an attacker needs to reach an isolated database through a simple attack path. The goal of this paper is to investigate the possibility of frustrating attackers by constructing a cloud network architecture that hides the path to a target asset in the network, utilizing multiple moving decoy virtual machines and confusing firewall configurations. A deceiving cloud network architecture can significantly delay attacks (by stretching the attack path from a handful of steps to thousands), providing time for system administrators to intervene and resolve the intrusion. This paper introduces the concept of misery digraphs, which provide a theoretical foundation for creating intrusion deception in clouds. This paper describes the necessary steps to convert a cloud to one that includes a misery digraph, and evaluates the feasibility and effectiveness of using the approach with Amazon Web Services. Our simulation results demonstrate that for a cloud implementing misery digraphs with a simple attack path of length five, there is a 91% probability that an attack requires at least 1000 steps to reach the target.

Securing the networks of large organizations is technically challenging due to the complex configurations and constraints. Managing these networks requires rigorous and comprehensive analysis tools. A network administrator needs to identify vulnerable configurations, as well as tools for hardening the networks. Such networks usually have dynamic and fluidic structures, thus one may have incomplete information about the connectivity and availability of hosts. In this paper, we address the problem of statically performing a rigorous assessment of a set of network security defense strategies with the goal of reducing the probability of a successful large-scale attack in a dynamically changing and complex network architecture. We describe a probabilistic graph model and algorithms for analyzing the security of complex networks with the ultimate goal of reducing the probability of successful attacks. Our model naturally utilizes a scalable state-of-the-art optimization technique called sequential linear programming that is extensively applied and studied in various engineering problems. In comparison to related solutions on attack graphs, our probabilistic model provides mechanisms for expressing uncertainties in network configurations, which is not reported elsewhere. We have performed comprehensive experimental validation with real-world network configuration data of a sizable organization.

BACKGROUND: Numerous tools have been developed to predict the fitness effects (i.e., neutral, deleterious, or beneficial) of genetic variants on corresponding proteins. However, prediction in terms of whether a variant causes the variant bearing protein to lose the original function or gain new function is also needed for better understanding of how the variant contributes to disease/cancer. To address this problem, the present work introduces and computationally defines four types of functional outcome of a variant: gain, loss, switch, and conservation of function. The deployment of multiple hidden Markov models is proposed to computationally classify mutations by the four functional impact types. RESULTS: The functional outcome is predicted for over a hundred thyroid stimulating hormone receptor (TSHR) mutations, as well as cancer related mutations in oncogenes or tumor suppressor genes. The results show that the proposed computational method is effective in fine grained prediction of the functional outcome of a mutation, and can be used to help elucidate the molecular mechanism of disease/cancer causing mutations. The program is freely available at http://bioinformatics.cs.vt.edu/zhanglab/HMMvar/download.php. CONCLUSION: This work is the first to computationally define and predict functional impact of mutations, loss, switch, gain, or conservation of function. These fine grained predictions can be especially useful for identifying mutations that cause or are linked to cancer.

The Fortran95 code VTDIRECT95, based on the original MPI, has been modified to use MPI-2. An option for VTDIRECT95 is to divide the feasible box into subdomains, and concurrently apply the global direct search algorithm DIRECT within each subdomain. When the number of subdomains is greater than one, a bug causes VTDIRECT95 to occasionally sample outside the given feasible box, which is serious if the objective function is not defined outside the given box. This bug has been fixed, and the sample output files have been updated to reflect the correction. For completeness, the package VTDIRECT95 now contains both the MPI-1 (with the multiple subdomain bug fixed) and the MPI-2 versions of the code.

BACKGROUND: With the development of sequencing technologies, more and more sequence variants are available for investigation. Different classes of variants in the human genome have been identified, including single nucleotide substitutions, insertion and deletion, and large structural variations such as duplications and deletions. Insertion and deletion (indel) variants comprise a major proportion of human genetic variation. However, little is known about their effects on humans. The absence of understanding is largely due to the lack of both biological data and computational resources. RESULTS: This paper presents a new indel functional prediction method HMMvar based on HMM profiles, which capture the conservation information in sequences. The results demonstrate that a scoring strategy based on HMM profiles can achieve good performance in identifying deleterious or neutral variants for different data sets, and can predict the protein functional effects of both single and multiple mutations. CONCLUSIONS: This paper proposed a quantitative prediction method, HMMvar, to predict the effect of genetic variation using hidden Markov models. The HMM based pipeline program implementing the method HMMvar is freely available at https://bioinformatics.cs.vt.edu/zhanglab/hmm.

With increasing public consciousness regarding sustainability, companies are ever more eager to introduce eco-friendly products and services. Assessing environmental footprints and designing sustainable products are challenging tasks since they require analysis of each component of a product through their life cycle. To achieve sustainable design of products, companies need to evaluate the environmental impact of their system, identify the major contributors to the footprint, and select the design alternative with the lowest environmental footprint. In this article, we formulate sustainable design as a series of clustering and classification problems, and propose a framework called AutoLCA that simplifies the effort of estimating the environmental footprint of a product bill of materials by more than an order of magnitude over current methods, which are mostly labor intensive. We apply AutoLCA to real data from a large computer manufacturer. We conduct a case study on bill of materials of four different products, perform a “hotspot” assessment analysis to identify major contributors to carbon footprint, and determine design alternatives that can reduce the carbon footprint from 1% to 36%.

Insulin secreted by pancreatic islet β-cells is the principal regulating hormone of glucose metabolism. It plays a key role in controlling glucose level in blood. Impairment of the pancreatic islet function may cause glucose to accumulate in the blood, and result in diabetes mellitus. In order to study the cause of dysfunction of pancreatic islets, a multiple-cell model containing healthy and unhealthy cells is proposed based on an existing single cell model. The β-cells in the model are connected through direct electrical connections between neighboring β-cells. The simulation results show that around 20% unhealthy cells in pancreatic islets will disrupt the insulin secretion. This suggests that a small portion of unhealthy cells may have greater effect in the dysfunction of insulin oscillation than expected.

This paper presents a new semiautomated soft classification method that is a hybrid between supervised and unsupervised classification algorithms for the classification of remote sensing data. Continuous iterative guided spectral class rejection (IGSCR) (CIGSCR) is based on the IGSCR classification method, a crisp classification method that automatically locates spectral classes within information class training data using clustering. This paper outlines the model and algorithm changes necessary to convert IGSCR to use soft clustering to produce soft classification in CIGSCR. This new algorithm addresses specific challenges presented by remote sensing data including large data sets (millions of samples), relatively small training data sets, and difficulty in identifying spectral classes. CIGSCR has many advantages over IGSCR, such as the ability to produce soft classification, less sensitivity to certain input parameters, potential to correctly classify regions that are not amply represented in training data, and a better ability to locate clusters associated with all classes. Furthermore, evidence is presented that the semisupervised clustering in CIGSCR produces more accurate classifications than classification based on clustering without supervision.

Significant effort has been devoted to designing clustering algorithms that are responsive to user feedback or that incorporate prior domain knowledge in the form of constraints. However, users desire more expressive forms of interaction to influence clustering outcomes. In our experiences working with diverse application scientists, we have identified an interaction style scatter/gather clustering that helps users iteratively restructure clustering results to meet their expectations. As the names indicate, scatter and gather are dual primitives that describe whether clusters in a current segmentation should be broken up further or, alternatively, brought back together. By combining scatter and gather operations in a single step, we support very expressive dynamic restructurings of data. Scatter/gather clustering is implemented using a nonlinear optimization framework that achieves both locality of clusters and satisfaction of user-supplied constraints. We illustrate the use of our scatter/gather clustering approach in a visual analytic application to study baffle shapes in the bat biosonar (ears and nose) system. We demonstrate how domain experts are adept at supplying scatter/gather constraints, and how our framework incorporates these constraints effectively without requiring numerous instance-level constraints.

BACKGROUND: The Structural Classification of Proteins (SCOP) database uses a large number of hidden Markov models (HMMs) to represent families and superfamilies composed of proteins that presumably share the same evolutionary origin. However, how the HMMs are related to one another has not been examined before. RESULTS: In this work, taking into account the processes used to build the HMMs, we propose a working hypothesis to examine the relationships between HMMs and the families and superfamilies that they represent. Specifically, we perform an all-against-all HMM comparison using the HHsearch program (similar to BLAST) and construct a network where the nodes are HMMs and the edges connect similar HMMs. We hypothesize that the HMMs in a connected component belong to the same family or superfamily more often than expected under a random network connection model. Results show a pattern consistent with this working hypothesis. Moreover, the HMM network possesses features distinctly different from the previously documented biological networks, exemplified by the exceptionally high clustering coefficient and the large number of connected components. CONCLUSIONS: The current finding may provide guidance in devising computational methods to reduce the degree of overlaps between the HMMs representing the same superfamilies, which may in turn enable more efficient large-scale sequence searches against the database of HMMs.

Insulin secreted by pancreatic islet β-cells is the principal regulating hormone of glucose metabolism. Disruption of insulin secretion may cause glucose to accumulate in the blood, and result in diabetes mellitus. Although deterministic models of the insulin secretion pathway are available, the stochastic aspect of the biological pathway has not been explored. As a first step in this direction, we present a hybrid model of the insulin secretion pathway, in which the delayed rectifying K+channels are treated as stochastic events. Simulation results of our hybrid model demonstrate that our model not only can reproduce the bursts of electrical activity as the deterministic model does, but also can be used to predict the magnitude of the total number of the delayed rectifying K+channels per cell needed in order to prevent the function of this pathway from disruption by stochastic effects. The coupling effect of multiple cells is also studied based on the hybrid model, which shows the synchronization behavior of the cells.

Modern data mining settings involve a combination of attribute-valued descriptors over entities as well as specified relationships between these entities. We present an approach to cluster such non-homogeneous datasets by using the relationships to impose either dependent clustering or disparate clustering constraints. Unlike prior work that views constraints as boolean criteria, we present a formulation that allows constraints to be satisfied or violated in a smooth manner. This enables us to achieve dependent clustering and disparate clustering using the same optimization framework by merely maximizing versus minimizing the objective function. We present results on both synthetic data as well as several real-world datasets.

Scattered data interpolation problems arise in many applications. Shepard’s method for constructing a global interpolant by blending local interpolants using local-support weight functions usually creates reasonable approximations. SHEPPACK is a Fortran 95 package containing five versions of the modified Shepard algorithm: quadratic (Fortran 95 translations of Algorithms 660, 661, and 798), cubic (Fortran 95 translation of Algorithm 791), and linear variations of the original Shepard algorithm. An option to the linear Shepard code is a statistically robust fit, intended to be used when the data is known to contain outliers. SHEPPACK also includes a hybrid robust piecewise linear estimation algorithm RIPPLE (residual initiated polynomial-time piecewise linear estimation) intended for data from piecewise linear functions in arbitrary dimension m . The main goal of SHEPPACK is to provide users with a single consistent package containing most existing polynomial variations of Shepard’s algorithm. The algorithms target data of different dimensions. The linear Shepard algorithm, robust linear Shepard algorithm, and RIPPLE are the only algorithms in the package that are applicable to arbitrary dimensional data.

This paper describes a new algorithm used to adaptively filter a remote-sensing data set based on signal-to-noise ratios (SNRs) once the maximum noise fraction has been applied. This algorithm uses Hermite splines to calculate the approximate area underneath the SNR curve as a function of band number, and that area is used to place bands into ldquobinsrdquo with other bands having similar SNRs. A median filter with a variable-sized kernel is then applied to each band, with the same size kernel used for each band in a particular bin. The proposed adaptive filters are applied to a hyperspectral image generated by the airborne visible/infrared imaging spectrometer sensor, and results are given for the identification of three different pine species located within the study area. The adaptive-filtering scheme improves image quality as shown by estimated SNRs. Classification accuracies of three pine species improved by more than 10% in the study area as compared to that achieved by the same discriminant method without adaptive spatial filtering.

VTDIRECT95 is a Fortran 95 implementation of D. R. Jones' deterministic global optimization algorithm called DIRECT , which is widely used in multidisciplinary engineering design, biological science, and physical science applications. The package includes both a serial code and a data-distributed massively parallel code for different problem scales and optimization (exploration vs. exploitation) goals. Dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel code employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing and scalability. In addition, checkpointing features are integrated into both versions to provide fault tolerance and hot restarts. Important algorithm modifications and design considerations are discussed regarding data structures, parallel schemes, error handling, and portability. Using several benchmark functions and real-world applications, the software is evaluated on different systems in terms of optimization effectiveness, data structure efficiency, parallel performance, and checkpointing overhead. The package organization and usage are also described in detail.

The chemical master equation, which is often considered as an accurate stochastic description of general chemical systems, usually imposes intensive computational requirements when used to characterize molecular biological systems. The major challenge comes from the curse of dimensionally, which has been tackled by a few research papers. The essential goal is to aggregate the system efficiently with limited approximation error. This paper presents an adaptive way to implement the aggregation process using information collected from Monte Carlo methods. Numerical results show the effectiveness of the proposed algorithm despite the lack of explicit estimation of approximation error.

This work is an intermediate step toward a fuzzy version of the iterative guided spectral class rejection (IGSCR) classification algorithm. IGSCR combines a clustering algorithm and a decision rule to produce multiple classifications. Although fuzzy versions of these algorithms are available, IGSCR can only evaluate hard clustering output. In an effort to move toward fuzzy classification output, this paper presents a statistically rigorous fuzzy cluster homogeneity test that is analogous to the discrete cluster homogeneity test.

The chemical master equation is considered an accurate description of general chemical systems, and especially so for modeling cell cycle and gene regulatory networks. This paper proposes an efficient way of solving the chemical master equation for some prototypical problems in systems biology. A comparison between this new approach and some traditional approaches is also given.

Abstract This work describes the Site‐Specific System Simulator for Wireless System Design (S4W), a problem‐solving environment (PSE) that integrates visualization and computational tools with a high‐level graphical user interface. S4W improves the ability of wireless system engineers to design an indoor wireless system by encouraging them to think in terms of designing the system for optimal performance. Issues of computation management, data management, and location of resources are hidden from the user. The complex nature of data sets in the domain of wireless simulations calls for a customized set of visualization tools. Therefore, a number ofad hocvisualizations were developed for S4W. A study comparing the integrated system with an earlier, unintegrated version is presented. This helps to demonstrate the productivity gains that a PSE provides. Copyright © 2007 John Wiley & Sons, Ltd.

ODRPACK (TOMS Algorithm 676) has provided a complete package for weighted orthogonal distance regression for many years. The code is complete with user selectable reporting facilities, numerical and analytic derivatives, derivative checking, and many more features. The foundation for the algorithm is a stable and efficient trust region Levenberg-Marquardt minimizer that exploits the structure of the orthogonal distance regression problem. ODRPACK95 was created to extend the functionality and usability of ODRPACK. ODRPACK95 adds bound constraints, uses the newer Fortran 95 language, and simplifies the interface to the user called subroutine.

Converting a biochemical reaction network to a set of kinetic rate equations is tedious and error prone. We describe known interface paradigms for inputing models of intracellular regulatory networks: graphical layout (diagrams), wizards, scripting languages, and direct entry of chemical equations. We present the JigCell Model Builder, which allows users to define models as a set of reaction equations using a spreadsheet (an example of direct entry of equations) and outputs model definitions in the Systems Biology Markup Language, Level 2. We present the results of two usability studies. The spreadsheet paradigm demonstrated its effectiveness in reducing the number of errors made by modelers when compared to hand conversion of a wiring diagram to differential equations. A comparison of representatives of the four interface paradigms for a simple model of the cell cycle was conducted which measured time, mouse clicks, and keystrokes to enter the model, and the number of screens needed to view the contents of the model. All four paradigms had similar data entry times. The spreadsheet and scripting language approaches require significantly fewer screens to view the models than do the wizard or graphical layout approaches.

Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked and handling singular solutions have made probability-one homotopy methods even more practical. POLSYS_GLP consists of Fortran 95 modules for finding all isolated solutions of a complex coefficient polynomial system of equations. The package is intended to be used on a distributed memory multiprocessor in conjunction with HOMPACK90 (Algorithm 777), and makes extensive use of Fortran 95-derived data types and MPI to support a general linear product (GLP) polynomial system structure. GLP structure is intermediate between the partitioned linear product structure used by POLSYS_PLP (Algorithm 801) and the BKK-based structure used by PHCPACK. The code requires a GLP structure as input, and although finding the optimal GLP structure is a difficult combinatorial problem, generally physical or engineering intuition about a problem yields a very good GLP structure. POLSYS_GLP employs a sophisticated power series end game for handling singular solutions, and provides support for problem definition both at a high level and via hand-crafted code. Different GLP structures and their corresponding Bezout numbers can be systematically explored before committing to root finding.

Summary form only given. We present a sophisticated and efficient parallel scheme for the DIRECT global optimization algorithm of Jones et al. (1993). Although several sequential implementations for this algorithm have been successfully applied to large scale MDO problems, few parallel versions of the DIRECT algorithm have addressed well algorithm characteristics such as a single starting point, an unpredictable workload, and a strong data dependency. These challenges engender many interesting design issues including domain decomposition, data access and management, and workload balancing. A hierarchical parallel scheme has been developed to address these challenges at three levels. Each level is supported by parallel and distributed data structures to access shared data sets, distribute workload, or exchange messages. Parameter estimation problems in systems biology provide an ideal application context for the present work. Global nonlinear parameter estimation results obtained on a 200 node Linux cluster are given for a cell cycle model for frog eggs.

SUMMARY: We describe the JigCell Model Builder (JCMB), a tool for creating biochemical reaction network models. JCMB is designed for ease of use and its interface uses the standard spreadsheet metaphor. The JigCell Run Manager (JCRM) is a tool for organizing the large collections of simulation runs typically required by reaction network modeling activities. AVAILABILITY: JCMB and JCRM are part of the JigCell suite available at http://jigcell.biol.vt.edu.

Digital libraries (DLs) are complex information systems and therefore demand formal foundations lest development efforts diverge and interoperability suffers. In this article, we propose the fundamental abstractions of Streams, Structures, Spaces, Scenarios, and Societies (5S), which allow us to define digital libraries rigorously and usefully. Streams are sequences of arbitrary items used to describe both static and dynamic (e.g., video) content. Structures can be viewed as labeled directed graphs, which impose organization. Spaces are sets with operations on those sets that obey certain constraints. Scenarios consist of sequences of events or actions that modify states of a computation in order to accomplish a functional requirement. Societies are sets of entities and activities and the relationships among them. Together these abstractions provide a formal foundation to define, relate, and unify concepts---among others, of digital objects, metadata, collections, and services---required to formalize and elucidate "digital libraries". The applicability, versatility, and unifying power of the 5S model are demonstrated through its use in three distinct applications: building and interpretation of a DL taxonomy, informal and formal analysis of case studies of digital libraries (NDLTD and OAI), and utilization as a formal basis for a DL description language.

A global optimization technique is applied to solve the optimal transmitter placement problem for indoor wireless systems. An efficient pattern search algorithm - DIviding RECTangles (DIRECT) of Jones et al.- has been connected to a parallel three-dimensional radio propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations. Surrogate functions for a parallel wideband code-division multiple-access (WCDMA) simulator were used to estimate the system performance for the global optimization algorithm. Power coverage and bit-error rate are considered as two different criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. This paper briefly describes the underlying radio propagation and WCDMA simulations and focuses on the design issues of the optimization loop.

Abstract As the power of computational Grids increases, there is a corresponding need for better usability for large and diverse communities. The focus in this paper is on supporting multidisciplinary communities of scientists and engineers. We discuss requirements for Grid computing environments (GCEs) in this context, and describe several core support technologies developed to meet these requirements. Our work extends the notion of a programming environment beyond the compile–schedule–execute paradigm, to include functionality such as collaborative application composition, information services, and data and simulation management. Systems designed for five different applications communities are described. These systems illustrate common needs and characteristics arising in multidisciplinary communities and motivate a high‐level design framework for building GCEs that meet those needs. Copyright © 2002 John Wiley & Sons, Ltd.

Globally convergent, probability-one homotopy methods have proven to be very effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based on probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked, and in the handling of singular solutions, have made probability-one homotopy methods even more practical. POLSYS_PLP consists of Fortran 90 modules for finding all isolated solutions of a complex coefficient polynomial system of equations. The package is intended to be used in conjunction with HOMPACK90 (Algorithm 777), and makes extensive use of Fortran 90 derived data types to support a partitioned linear product (PLP) polynomial system structure. PLP structure is a generalization of m -homogeneous structure, whereby each component of the system can have a different m -homogeneous structure. The code requires a PLP structure as input, and although finding the optimal PLP structure is a difficult combinatorial problem, generally physical or engineering intuition about a problem yields a very good structure. POLSYS_PLP employs a sophisticated power series end game for handling singular solutions, and provides support for problem definition both at a high level and via hand-crafted code. Different PLP structures and their corresponding Bezout

We describe a visualization tool to aid aircraft designers during the conceptual design stage. The conceptual design for an aircraft is defined by a vector of 10-30 parameters. The goal is to find a vector that minimizes an objective function while meeting a series of constraints. VizCraft integrates the simulation code that evaluates the design with visualizations for analyzing the design individually or in contrast to other designs. VizCraft allows the designer to easily switch between the view of a design in the form of a parameter set, and a visualization of the corresponding aircraft. The user can easily see which, if any, constraints are violated. VizCraft also allows the user to view a database of designs using parallel coordinates.

Multidisciplinary design optimization (MDO) for large-scale engineering problems poses many challenges (e.g. the design of an efficient concurrent paradigm for global optimization based on disciplinary analyses, expensive computations over vast data sets, etc.). This work focuses on the application of distributed schemes for massively parallel architectures to MDO problems, as a tool for reducing computation time and solving larger problems. The specific problem considered here is configuration optimization of a high speed civil transport (HSCT), and the efficient parallelization of the embedded paradigm for reasonable design space identification. Two distributed dynamic load balancing techniques (random polling and global round robin with message combining) and two necessary termination detection schemes (global task count and token passing) were implemented and evaluated in terms of effectiveness and scalability to large problem sizes and a thousand processors. The effect of certain parameters on execution time was also inspected. Empirical results demonstrated stable performance and effectiveness for all schemes, and the parametric study showed that the selected algorithmic parameters have a negligible effect on performance. Copyright © 1999 John Wiley & Sons, Ltd.

Applications involving large sparse nonsymmetric linear systems encourage parallel implementations of robust iterative solution methods, such as GMRES(k). One variation of GMRES(k) is to adapt the restart value k for any given problem and use Householder reflections in the orthogonalization phase to achieve high accuracy. The Householder transformations can be performed without global communications and modified to use an arbitrary row distribution of the coefficient matrix. The effect of this modification on the GMRES(k) performance is discussed here. This paper compares the abilities of various parallel GMRES(k) implementations to maintain fixed efficiency with increase in problem size and number of processors.

We describe an aircraft design problem in high dimensional space, with D typically being 10 to 30. In some respects this is a classic optimization problem, where the goal is to find the point that minimizes an objective function while satisfying a set of constraints. However, evaluating an individual point is expensive, and the high dimensionality makes many approaches to solving the problem infeasible. The difficulty of the problem means that aircraft designers would benefit from any insights that can be provided. We discuss how simple visualizations have already proved beneficial, and then describe how visualization might be of further help in the future.

The compression and decompression of continuous-tone images is important in document management and transmission systems. This paper considers an alternative image representation scheme, based on Gaussian derivatives, to the standard discrete cosine transformation (DCT), within a Joint Photographic Experts Group (JPEG) framework. Depending on the computer arithmetic hardware used, the approach developed might yield a compression/decompression technique twice as fast as the DCT and of (essentially) equal quality.

HOMPACK90 is a Fortran 90 version of the Fortran 77 package HOMPACK (Algorithm 652), a collection of codes for finding zeros or fixed points of nonlinear systems using globally convergent probability-one homotopy algorithms.Three qualitatively different algorithmsordinary differential equation based, normal flow, quasi-Newton augmented Jacobian matrix-are provided for tracking homotopy zero curves, as well as separate routines for dense and sparse Jacobian matrices.A high level driver for the special case of polynomial systems is also provided.Changes to HOMPACK include numerous minor improvements, simpler and more elegant interfaces, use of modules, new end games, support for several sparse matrix data structures, and new iterative algorithms for large sparse Jacobian matrices.

Homotopy algorithms to solve a nonlinear system of equations f(x) = 0 involve tracking the zero curve of a homotopy map p(a, λ, x) from λ = 0 until λ = 1. When the algorithm nears or crosses the hyperplane λ = 1, an “end game” phase is begun to compute the solution x¯ satisfying p(a, λ, x¯) = f(x¯) = 0. This note compares several end game strategies, including the one implemented in the normal flow code FIXPNF in the homotopy software package HOMPACK.

Efficient and robust computation of one or more of the operating points of a nonlinear circuit is a necessary first step in a circuit simulator. The application of globally convergent probability-one homotopy methods to various systems of nonlinear equations that arise in circuit simulation is discussed. The coercivity conditions required for such methods are established using concepts from circuit theory. The theoretical claims of global convergence for such methods are substantiated by experiments with a collection of examples that have proved difficult for commercial simulation packages that do not use homotopy methods. Moreover, by careful design of the homotopy equations, the performance of the homotopy methods can be made quite reasonable. An extension to the steady-state problem in the time domain is also discussed.>

Three approaches to parallelizing important components of the mathematical software package ELLPACK are considered: an explicit approach using compiler directives available only on the target machine, an automatic approach using an optimizing and parallelizing precompiler, and a two-level approach based on extensive use of a set of low level computational kernels. The focus is on shared memory architectures. Each approach to parallelization is described in detail, along with a discussion of the effort involved. Performance on a test problem, using up to sixteen processors of a Sequent Symmetry S81, is reported and discussed. Implications for the parallelization of a broad class of mathematical software are drawn.

Embedding algorithms used to solve nonlinear systems of equations do so by constructing a continuous family of systems and solving the given system by tracking the continuous curve of solutions to the family. Solving nonlinear equations by a globally convergent embedding algorithm requires the evaluation and factoring of a Jacobian matrix at many points along the embedding curve. Ways to optimize the Jacobian matrix on a hypercube are described. Several static and dynamical strategies for assigning components of the Jacobian to processors on the hypercube are investigated. It is found that a static rectangular grid mapping is the preferred choice for inclusion in a robust parallel mathematical software package. The static linear mapping is a viable alternative when there are many common subexpressions in the component evaluation, and the dynamic assignment strategy should only be considered when there is large variation in the evaluation times for the components, leading to a load imbalance on the processors.>

Although the theory of polynomial continuation has been established for over a decade (following the work of Garcia, Zangwill, and Drexler), it is difficult to solve polynomial systems using continuation in practice. Divergent paths (solutions at infinity), singular solutions, and extreme scaling of coefficients can create catastrophic numerical problems. Further, the large number of paths that typically arise can be discouraging. In this paper we summarize polynomial-solving homotopy continuation and report on the performance of three standard path-tracking algorithms (as implemented in HOMPACK) in solving three physical problems of varying degrees of difficulty. Our purpose is to provide useful information on solving polynomial systems, including specific guidelines for homotopy construction and parameter settings. The m -homogeneous strategy for constructing polynomial homotopies is outlined, along with more traditional approaches. Computational comparisons are included to illustrate and contrast the major HOMPACK options. The conclusions summarize our numerical experience and discuss areas for future research.

It is a common practice in computer vision and image processing to convolve rectangular constant coefficient windows with digital images to perform local smoothing and derivative estimation for edge detection and other purposes. If all data points in each image window belong to the same statistical population, this practice is reasonable and fast. But, as is well known, constant coefficient window operators produce incorrect results if more than one statistical population is present within a window, for example, if a gray-level or gradient discontinuity is present. This paper shows one way to apply the theory of robust statistics to the data smoothing and derivative estimation problem. A robust window operator is demonstrated that preserves gray-level and gradient discontinuities in digital images as it smooths and estimates derivatives.

There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK provides three qualitatively different algorithms for tracking the homotopy zero curve: ordinary differential equation-based, normal flow, and augmented Jacobian matrix. Separate routines are also provided for dense and sparse Jacobian matrices. A high-level driver is included for the special case of polynomial systems.

A constrained transform coding procedure is developed which is a combination of transform coding with differential pulse code modulation. The algorithm avoids block boundary mismatch errors, yet retains the coding efficiency of transform coding. A general theory of constrained transform coding is developed which includes the discrete cosine transformation and tensor products of splines as special cases. Results using the cosines and spines are given for two images. A complete discussion of the necessary linear algebra background is also given.

This paper describes a new method to be used for matching three-dimensional objects with curved surfaces to two-dimensional perspective views. The method requires for each three-dimensional object a stored model consisting of a closed space curve representing some characteristic connected curved edges of the object. The input is a two-dimensional perspective projection of one of the stored models represented by an ordered sequence of points. The input is converted to a spline representation which is sampled at equal intervals to derive a curvature function. The Fourier transform of the curvature function is used to represent the shape. The actual matching is reduced to a minimization problem which is handled by the Levenberg-Marquardt algorithm [3].

of a homotopy map, fixed points of nonhnear systems, zeros of nonhnear systems CR Categories 5 15 Language Fortran