In this paper, a framework for shape-based similarity search of 3D molecular structures is presented. The proposed framework exploits simultaneously the discriminative capabilities of a global, a local, and a hybrid local-global shape feature to produce a geometric descriptor that achieves higher retrieval accuracy than each feature does separately. Global and hybrid features are extracted using pairwise computations of diffusion distances between the points of the molecular surface, while the local feature is based on accumulating pairwise relations among oriented surface points into local histograms. The local features are integrated into a global descriptor vector using the bag-of-features approach. Due to the intrinsic property of its constituting shape features to be invariant to articulations of the 3D objects, the framework is appropriate for similarity search of flexible 3D molecules, while at the same time it is also accurate in retrieving rigid 3D molecules. The proposed framework is evaluated in flexible and rigid shape matching of 3D protein structures as well as in shape-based virtual screening of large ligand databases with quite promising results.

In this paper, a framework for protein-protein docking is proposed, which exploits both shape and physicochemical complementarity to generate improved docking predictions. Shape complementarity is achieved by matching local surface patches. However, unlike existing approaches, which are based on single-patch or two-patch matching, we developed a new algorithm that compares simultaneously, groups of neighboring patches from the receptor with groups of neighboring patches from the ligand. Taking into account the fact that shape complementarity in protein surfaces is mostly approximate rather than exact, the proposed group-based matching algorithm fits perfectly to the nature of protein surfaces. This is demonstrated by the high performance that our method achieves especially in the case where the unbound structures of the proteins are considered. Additionally, several physicochemical factors, such as desolvation energy, electrostatic complementarity (EC), hydrophobicity (HP), Coulomb potential (CP), and Lennard-Jones potential are integrated using an optimized scoring function, improving geometric ranking in more than 60 percent of the complexes of Docking Benchmark 2.4.

In this paper, a novel approach for fast protein-protein docking based on geometric complementarity is introduced. Complementarity matching is achieved using a rotation-invariant 3D shape descriptor, the Shape Impact Descriptor (SID). Rotation invariance enables matching of equally-sized surface patches without the need for initial alignment. The candidate poses are computed using an intuitive alignment method, which is much faster than exhaustively searching the translational and rotational space of the ligand. The method yields competitive results when compared to other well-known geometry-based, rigid-docking approaches.

This paper presents a novel approach for fast rigid docking of proteins based on geometric complementarity. After extraction of the 3D molecular surface, a set of local surface patches is generated based on the local surface curvature. The shape complementarity between a pair of patches is calculated using an efficient shape descriptor, the Shape Impact Descriptor. The key property of the Shape Impact Descriptor is its rotation invariance, which obviates the need for taking an exhaustive set of rotations for each pair of patches. Thus, complementarity matching between two patches is reduced to a simple histogram matching. Finally, a condensed set of almost complementary pairs of surface patches is supplied as input to the final scoring step, where each pose is evaluated using a 3D distance grid. The experimental results prove that the proposed method demonstrates superior performance over other well-known geometry-based, rigid-docking approaches.

We present the design and the basic features of a computer learning environment for programming and C using geometrical objects (L.E.C.G.O.). The design of this environment was the result of modeling. Basic aspects of constructivism have also been taken into account in its design. L.E.C.G.O. provides pupils with opportunities to: a) express their problem solving strategies in multiple representation systems starting from intuitive representations and moving gradually to more sophisticated ones, b) solve a variety of familiar and meaningful problems, and c) overcome the cognitive load of the syntactical rules of programming in C by using appropriately designed computer-based authoring tools. A similar environment has not yet been reported.

This paper describes the integration of a multidatabase system and a knowledge-base system to support the data-integration component of a data warehouse. The multidatabase system integrates various component databases with a common query language; however, it does not provide capability for schema integration and other utilities necessary for data warehousing. In addition, the knowledge base system offers a declarative logic language with second-order syntax but first-order semantics for integrating the schemes of the data sources into the warehouse and for defining complex, recursively defined materialized views. Furthermore, deductive rules are also used for cleaning, checking the integrity and summarizing the data imported into the data warehouse. The knowledge base system features an efficient incremental view maintenance mechanism that is used for refreshing the data warehouse, without querying the data sources.

Abstract We outline the design of a recommendation system (MyPYTHIA) implemented as a Web portal. MyPYTHIA's design objectives include evaluating the quality and performance of scientific software on Grid platforms, creating knowledge about which software and computational services should be selected for solving particular problems, selecting parameters of software (or of computational services) based on user‐specified computational objectives, providing access to performance data and knowledge bases over the Web and enabling recommendations for targeted application domains. MyPYTHIA uses a combination of statistical analysis, pattern extraction techniques and a database of software performance to map feature‐based representations of problem instances to appropriate software. MyPYTHIA's open architecture allows the user to customize it for conducting individual case studies. We describe the architecture as well as several scientific domains of knowledge enabled by such case studies. Copyright © 2002 John Wiley & Sons, Ltd.

The traditional approach for estimating the performance of numerical methods is to combine an operation's count with an asymptotic error analysis. This analytic approach gives a general feel of the comparative efficiency of methods, but it rarely leads to very precise results. It is now recognized that accurate performance evaluation can be made only with actual measurements on working software. Given that such an approach requires an enormous amount of performance data related to actual measurements, the development of novel approaches and systems that intelligently and efficiently analyze these data is of great importance to scientists and engineers. The paper presents intelligent knowledge acquisition approaches and an integrated prototype system, which enables the automatic and systematic analysis of performance data. The system analyzes the performance data which is usually stored in a database with statistical, and inductive learning techniques and generates knowledge which can be incorporated in a knowledge base incrementally. We demonstrate the use of the system in the context of a case study, covering the analysis of numerical algorithms for the pricing of American vanilla options in a Black and Scholes modeling framework. We also present a qualitative and quantitative comparison of two techniques used for the automated knowledge acquisition phase.

editorial Free Access Share on Editorial: special issue in honor of John Rice's 65th birthday Authors: Ronald Boisvert National Institute of Standards and Technology, Gaithersburg, MD National Institute of Standards and Technology, Gaithersburg, MDView Profile , Wayne Dyksen View Profile , Elias Houstis Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 26Issue 201 June 2000https://doi.org/10.1145/353474.354094Published:01 June 2000Publication History 1citation367DownloadsMetricsTotal Citations1Total Downloads367Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Often scientists need to locate appropriate software for their problems and then select from among many alternatives. We have previously proposed an approach for dealing with this task by processing performance data of the targeted software. This approach has been tested using a customized implementation referred to as PYTHIA. This experience made us realize the complexity of the algorithmic discovery of knowledge from performance data and of the management of these data together with the discovered knowledge. To address this issue, we created PYTHIA-II—a modular framework and system which combines a general knowledge discovery in databases (KDD) methodology and recommender system technologies to provide advice about scientific software/hardware artifacts. The functionality and effectiveness of the system is demonstrated for two existing performance studies using sets of software for solving partial differential equations. From the end-user perspective, PYTHIA-II allows users to specify the problem to be solved and their computational objectives. In turn, PYTHIA-II (i) selects the software available for the user's problem (ii) suggests parameter values, and (iii) assesses the recommendation provided. PYTHIA-II provides all the necessary facilities to set up database schemas for testing suites and associated performance data in order to test sets of software. Moreover, it allows easy interfacing of alternative data mining and recommendation facilities. PYTHIA-II is an open-ended system implemented on public domain software and has been used for performance evaluation in several different problem domains.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

Presents the design and prototype implementation of a system built around the FINANZIA system that aims in the automated analysis and classification of option pricing algorithms based on experimental data. The main objective is to assist in the generation, storage and evaluation of large amounts of experimental option pricing data and to facilitate the identification of performance properties of the pricing algorithms with respect to the various problems. The analysis of the data is achieved using statistical and inductive logic techniques and the identified properties are used to expand the knowledge base. We demonstrate the use of the system in the context of a case study covering the pricing of American vanilla options in a Black & Scholes (1973) modeling framework.

The article presents the software architecture and implementation of the problem-solving environment (PSE) PELLPACK for modeling physical objects described by partial differential equations (PDEs). The scope of this PSE is broad, as PELLPACK incorporates many PDE solving systems, and some of these, in turn, include several specific PDE solving methods. Its coverage for 1D, 2D. and 3D elliptic or parabolic problems is quite broad, and it handles some hyperbolic problems, Since a PSE should provided complete support for the problem-solving process, PELLPACK also contains a large amount of code to support graphical user interfaces, analystic tools, user help, domain or mesh partitioning, machine and data selection, visualization, and various other tasks. Its total size is well over 1 million lines code. Its open-ended software architecture consists of several software layers. The top layer is an interactive graphical interface for specifying the PDE model and its solution framework This interface saves that results of the user specification in the form of a very high level PDE language which is an alternative interface to the PELLPACK system. This language also allows a user to specify the PDE problem and its solution framework textually in a natural form. The PELLPACK language preprocessor generates a Fortran control program with the interfaces, calls to specified components and libraries of the PDE solution framework, and functions defining the PDE problem. The PELLPACK program execution is supported by a hign-level tool where the virtual parallel system is defined, where the compilation, loading, and execution are controlled. Finally, the PELLPACK PSE integrates several PDE libraries and PDE systems based on the decomposition of discrete geometric data to map sparse PDE computations to parallel machines. An instance of the system is available as aWeb server(WebPELLPACK) for public use at http://pellpack.cs.purdue.edu.

Neurofuzzy approaches for predicting financial time series are investigated and shown to perform well in the context of various trading strategies involving stocks and options. The horizon of prediction is typically a few days and trading strategies are examined using historical data. Two methodologies are presented wherein neural predictors are used to anticipate the general behavior of financial indexes (moving up, down, or staying constant) in the context of stocks and options trading. The methodologies are tested with actual financial data and show considerable promise as a decision making and planning tool.

Neurofuzzy characterization of financial time series refers to the judicious application of neural and fuzzy tools to the problem of time series prediction. A methodology is presented where fuzzy if/then rules and neural predictors are used to anticipate the predictability a time series over various time horizons. The methodology is tested with actual financial time series data (S&S 500 daily closes) and shows considerable promise as a decision making and planning tool. Results in the context of option trading strategies are presented and discussed.

Advances in wired and wireless networking technologies are making networked computing the most common form of high performance computing. Similarly, software like Mosaic and Netscape have not only unified the networked computing landscape, but they have made it available to the masses in a simple, machine independent way. These developments are changing the way we do computational science, learn, research, collaborate, access information and resources, and maintain local and global relations. We envision a scenario where large scale computational science and engineering applications like virtual classrooms and laboratories are ubiquitous, and information resources are accessible on-demand from anywhere. In this paper we present the design of a user interface that will be appropriate to this scenario. We argue that interfaces modeled on the pen and paper paradigm are suited in this context. Specifically, we present the software architecture of a notebook interface. We lay down the requirements for such an interface and present its implementation using the World Wide Web. A realization of the notebook model is presented for a problem solving environment (PDELab) to support the numerical simulation of PDE based applications on a network of heterogeneous high performance machines. © 1997 John Wiley & Sons, Ltd.

In this paper, we propose two new neuro-fuzzy schemes, one for classification and one for clustering problems. The classification scheme is based on Simpson's fuzzy min-max method (1992, 1993) and relaxes some assumptions he makes. This enables our scheme to handle mutually nonexclusive classes. The neuro-fuzzy clustering scheme is a multiresolution algorithm that is modeled after the mechanics of human pattern recognition. We also present data from an exhaustive comparison of these techniques with neural, statistical, machine learning, and other traditional approaches to pattern recognition applications. The data sets used for comparisons include those from the machine learning repository at the University of California, Irvine. We find that our proposed schemes compare quite well with the existing techniques, and in addition offer the advantages of one-pass learning and online adaptation.

Problem-solving e*nvironments (PSEs) interact with the user in a language “natural” to the associated discipline, and they provide a high-level abstraction of the underlying, computationally complex model. The knowledge-based system PYTHIA addresses the problem of (parameter, algorithm) pair selection within a scientific computing domain assuming some minimum user-specified computational objectives and some characteristics of the given problem. PYTHIA's framework and methodology are general and applicable to any class of scientific problems and solvers. PYTHIA is applied in the context of Parallel ELLPACK where there are many alternatives for the numerical solution of elliptic partial differential equations (PDEs). PYTHIA matches the characteristics of the given problem with those of PDEs in an existing problem population and then uses performance profiles of the various solvers to select the appropriate method given user-specified error and solution time bounds. The profiles are automatically generated for each solver of the Parallel ELLPACK library.— Authors' Abstract

We consider computations associated with data parallel iterative solvers used for the numerical solution of partial differential equations (PDEs). The mapping of such computations into load balanced tasks requiring minimum synchronization and communication is a difficult combinatorial optimization problem. Its optimal solution is essential for the efficient parallel processing of PDE computations. Determining data mappings that optimize a number of criteria, like workload balance, synchronization, and local communication, often involves the solution of an NP-Complete problem. Although data mapping algorithms have been known for a few years, there is lack of qualitative and quantitative comparisons based on the actual performance of the parallel computation. In this paper we present two new data mapping algorithms and evaluate them together with a large number of existing ones using the actual performance of data parallel iterative PDE solvers on the nCUBE II. Comparisons on the performance of data parallel iterative PDE solvers on medium and large scale problems demonstrate that some computationally inexpensive data block partitioning algorithms are as effective as the computationally expensive deterministic optimization algorithms. Also, these comparisons demonstrate that the existing approach in solving the data partitioning problem is inefficient for large scale problems. Finally, a software environment for the solution of the partitioning problem of data parallel iterative solvers is presented.

In this paper we formulate new mapping strategies for partial differential equations

In this paper we study the partitioning and allocation of computations associated with the numerical solution of partial differential equations (PDEs). Strategies for the mapping of such computations to parallel MIMD architectures can be applied to different levels of the solution process. We introduce and study heuristic approaches defined on the associated geometric data structures (meshes). Specifically, we study methods for decomposing finite element and finite difference meshes into balanced, nonoverlapping subdomains which guarantee minimum communication and synchronization among the underlying associated subcomputations. Two types of algorithms are considered: clustering techniques based on sequential orderings of the discrete geometric data and optimization based techniques involving geometric or graphical metric criteria. These algorithms support the automatic mode of a geometry decomposition tool developed in the parallel ELLPACK environment which is implemented under X11-window systems. A brief description of this tool is presented.

In the parallel ELLPACK (//ELLPACK) project we are developing a library of parallel interative methods for distributed memory multiprocessor systems and software tools for partitioning and allocation of the underlying computations. In this paper we discuss the implementation issues within the //ELLPACK environment and present preliminary performance results of some of the modules on three hypercube based architectures: NCUBE, iPSC/1 and iPSC/2. These results indicate that the iterative methods are capable of delivering close to optimal scaled speed-ups while the combination of concurrent/vector processing can lead to sizable improvements of the overall performance. These experiments have shown that distributed memory systems are capable of solving significantly large problems effectively.

We consider the integration of a domain decomposition technique with a new quadratic spline collocation discretization scheme for solving second order elliptic boundary value problems on rectangles. The domain decomposition method is based on the capacitance matrix technique. Due to the limitations of existing methods for solving the corresponding capacitance problem, we develop and analyze iterative methods for its solution. The optimum partitioning and mapping of the underlying computation is studied on hypercube architectures. A numerical realization of this method is presented on NCUBE/7 (128 processors) and its comparative efficiency is measured. The resulting parallel quadratic spline collocation-capacitance method is seen to be efficient in achieving accurate solutions and in using parallel architectures.

We consider the collocation method for linear, second-order elliptic problems on rectangular and general two-dimensional domains. An overview of the method is given for general domains, followed by a discussion of the improved efficiencies and simplifications possible for rectangular domains. A very-high-level description is given of three specific collocation algorithms that use Hermite bicubic basic functions, (1) GENCOL (collocation on general two-dimensional domains), (2) HERMCOL (collocation on rectangular domains with general linear boundary conditions), and (3) INTCOL (collocation on rectangular domains with uncoupled boundary conditions). The linear system resulting from INTCOL has half the bandwidth of that from HERMCOL, which provides substantial benefit in solving the system. We provide some examples showing the range of applicability of the algorithms and some performance profiles illustrating their efficiency. Fortran implementations of these algorithms are given in the companion papers [10, 11].

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 637: GENCOL: collocation of general domains with bicubic hermite polynomials Authors: E. N. Houstis Purdue Univ. and Univ. of Thessaloniki Purdue Univ. and Univ. of ThessalonikiView Profile , W. F. Mitchell Purdue Univ. Purdue Univ.View Profile , J. R. Rice Purdue Univ. Purdue Univ.View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 4Dec. 1985 pp 413–415https://doi.org/10.1145/6187.6194Published:01 December 1985Publication History 13citation376DownloadsMetricsTotal Citations13Total Downloads376Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 638: INTCOL and HERMCOL: collocation on rectangular domains with bicubic hermite polynomials Authors: E. N. Houstis Purdue Univ. and Univ. of Thessaloniki Purdue Univ. and Univ. of ThessalonikiView Profile , W. F. Mitchell Purdue Univ. Purdue Univ.View Profile , J. R. Rice Purdue Univ. Purdue Univ.View Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 11Issue 4Dec. 1985 pp 416–418https://doi.org/10.1145/6187.6195Online:01 December 1985Publication History 14citation374DownloadsMetricsTotal Citations14Total Downloads374Last 12 Months10Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An algorithm for approximating certain classes of elliptic partial differential equations on a rectangle is presented.The algorithm uses high-order 9-point difference approximations to the Helmholtz-type (fourth-order) or Polsson (sixth-order) equations and the fast Fourier transform.Compared to efficient second-order fast direct methods for smooth problems, the execution time is reduced by a large factor, typically 50 for the Helmholtz-type equations and over 100 for the Poisson problem.Comparisons with two high-order fast direct methods indicate the superiority of the algorithm.

article Free AccessArtifacts Evaluated & ReusableArtifacts Available Share on Algorithm 543: FFT9, Fast Solution of Helmholtz-Type Partial Differential Equations [D3] Authors: E. N. Houstis Department of Computer Science, Purdue University, West Lafayette, IN Department of Computer Science, Purdue University, West Lafayette, INView Profile , T. S. Papatheodorou Department of Mathematics, Clarkson College of Technology, Potsdam, NY Department of Mathematics, Clarkson College of Technology, Potsdam, NYView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 5Issue 4Dec. 1979 pp 490–493https://doi.org/10.1145/355853.355865Online:01 December 1979Publication History 7citation402DownloadsMetricsTotal Citations7Total Downloads402Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper describes a system to systematically compare the performance of various methods (software modules) for the numerical solution of partial differential equations. We discuss the general nature and large size of this performance evaluation problem and the data one obtains. The system meets certain design objectives that ensure a valid experiment: 1) precise definition of a particular measurement; 2) uniformity in defimition of variables entering the experiment; and 3) reproducibility of results. The ease of use of the system makes it possible to make the large sets of measurements necessary to obtain confidence in the results and its portability allows others to check or extend the measurements. The system has four parts: 1) semiautomatic generation of problems for experimental input; 2) the ELLPACK system for actually solving the equation; 3) a data management system to organize and access the experimental data; and 4) data analysis programs to extract graphical and statistical summaries from the data.