Digital Commons Network^™

The “Knapsack Problem” Workbook: An Exploration Of Topics In Computer Science, Steven Cosares

Open Educational Resources

This workbook provides discussions, programming assignments, projects, and class exercises revolving around the “Knapsack Problem” (KP), which is widely a recognized model that is taught within a typical Computer Science curriculum. Throughout these discussions, we use KP to introduce or review topics found in courses covering topics in Discrete Mathematics, Mathematical Programming, Data Structures, Algorithms, Computational Complexity, etc. Because of the broad range of subjects discussed, this workbook and the accompanying spreadsheet files might be used as part of some CS capstone experience. Otherwise, we recommend that individual sections be used, as needed, for exercises relevant to a course in …

Lecture 14: Randomized Algorithms For Least Squares Problems, Ilse C.F. Ipsen

Mathematical Sciences Spring Lecture Series

The emergence of massive data sets, over the past twenty or so years, has lead to the development of Randomized Numerical Linear Algebra. Randomized matrix algorithms perform random sketching and sampling of rows or columns, in order to reduce the problem dimension or compute low-rank approximations. We review randomized algorithms for the solution of least squares/regression problems, based on row sketching from the left, or column sketching from the right. These algorithms tend to be efficient and accurate on matrices that have many more rows than columns. We present probabilistic bounds for the amount of sampling required to achieve a …

Lecture 13: A Low-Rank Factorization Framework For Building Scalable Algebraic Solvers And Preconditioners, X. Sherry Li

Mathematical Sciences Spring Lecture Series

Factorization based preconditioning algorithms, most notably incomplete LU (ILU) factorization, have been shown to be robust and applicable to wide ranges of problems. However, traditional ILU algorithms are not amenable to scalable implementation. In recent years, we have seen a lot of investigations using low-rank compression techniques to build approximate factorizations.
A key to achieving lower complexity is the use of hierarchical matrix algebra, stemming from the H-matrix research. In addition, the multilevel algorithm paradigm provides a good vehicle for a scalable implementation. The goal of this lecture is to give an overview of the various hierarchical matrix formats, such …

Lecture 03: Hierarchically Low Rank Methods And Applications, David Keyes

Mathematical Sciences Spring Lecture Series

As simulation and analytics enter the exascale era, numerical algorithms, particularly implicit solvers that couple vast numbers of degrees of freedom, must span a widening gap between ambitious applications and austere architectures to support them. We present fifteen universals for researchers in scalable solvers: imperatives from computer architecture that scalable solvers must respect, strategies towards achieving them that are currently well established, and additional strategies currently being developed for an effective and efficient exascale software ecosystem. We consider recent generalizations of what it means to “solve” a computational problem, which suggest that we have often been “oversolving” them at the …

Lecture 02: Tile Low-Rank Methods And Applications (W/Review), David Keyes

Mathematical Sciences Spring Lecture Series

As simulation and analytics enter the exascale era, numerical algorithms, particularly implicit solvers that couple vast numbers of degrees of freedom, must span a widening gap between ambitious applications and austere architectures to support them. We present fifteen universals for researchers in scalable solvers: imperatives from computer architecture that scalable solvers must respect, strategies towards achieving them that are currently well established, and additional strategies currently being developed for an effective and efficient exascale software ecosystem. We consider recent generalizations of what it means to “solve” a computational problem, which suggest that we have often been “oversolving” them at the …

A Mathematical Framework On Machine Learning: Theory And Application, Bin Shi

FIU Electronic Theses and Dissertations

The dissertation addresses the research topics of machine learning outlined below. We developed the theory about traditional first-order algorithms from convex opti- mization and provide new insights in nonconvex objective functions from machine learning. Based on the theory analysis, we designed and developed new algorithms to overcome the difficulty of nonconvex objective and to accelerate the speed to obtain the desired result. In this thesis, we answer the two questions: (1) How to design a step size for gradient descent with random initialization? (2) Can we accelerate the current convex optimization algorithms and improve them into nonconvex objective? For application, …

Minimizing Differences Of Convex Functions With Applications To Facility Location And Clustering, Mau Nam Nguyen, R. Blake Rector, Daniel J. Giles

Mathematics and Statistics Faculty Publications and Presentations

In this paper we develop algorithms to solve generalized Fermat-Torricelli problems with both positive and negative weights and multifacility location problems involving distances generated by Minkowski gauges. We also introduce a new model of clustering based on squared distances to convex sets. Using the Nesterov smoothing technique and an algorithm for minimizing differences of convex functions called the DCA introduced by Tao and An, we develop effective algorithms for solving these problems. We demonstrate the algorithms with a variety of numerical examples.

Filters And Matrix Factorization, Myung-Sin Song, Palle E. T. Jorgensen

SIUE Faculty Research, Scholarship, and Creative Activity

We give a number of explicit matrix-algorithms for analysis/synthesis

in multi-phase filtering; i.e., the operation on discrete-time signals which

allow a separation into frequency-band components, one for each of the

ranges of bands, say N , starting with low-pass, and then corresponding

filtering in the other band-ranges. If there are N bands, the individual

filters will be combined into a single matrix action; so a representation of

the combined operation on all N bands by an N x N matrix, where the

corresponding matrix-entries are periodic functions; or their extensions to

functions of a complex variable. Hence our setting entails …

Nonsmooth Algorithms And Nesterov's Smoothing Technique For Generalized Fermat-Torricelli Problems, Nguyen Mau Nam, Nguyen Thai An, R. Blake Rector, Jie Sun

Mathematics and Statistics Faculty Publications and Presentations

We present algorithms for solving a number of new models of facility location which generalize the classical Fermat--Torricelli problem. Our first approach involves using Nesterov's smoothing technique and the minimization majorization principle to build smooth approximations that are convenient for applying smooth optimization schemes. Another approach uses subgradient-type algorithms to cope directly with the nondifferentiability of the cost functions. Convergence results of the algorithms are proved and numerical tests are presented to show the effectiveness of the proposed algorithms.

Data Mining Based Hybridization Of Meta-Raps, Fatemah Al-Duoli, Ghaith Rabadi

Engineering Management & Systems Engineering Faculty Publications

Though metaheuristics have been frequently employed to improve the performance of data mining algorithms, the opposite is not true. This paper discusses the process of employing a data mining algorithm to improve the performance of a metaheuristic algorithm. The targeted algorithms to be hybridized are the Meta-heuristic for Randomized Priority Search (Meta-RaPS) and an algorithm used to create an Inductive Decision Tree. This hybridization focuses on using a decision tree to perform on-line tuning of the parameters in Meta-RaPS. The process makes use of the information collected during the iterative construction and improvement phases Meta-RaPS performs. The data mining algorithm …

Commuting Smoothed Projectors In Weighted Norms With An Application To Axisymmetric Maxwell Equations, Jay Gopalakrishnan, Minah Oh

Mathematics and Statistics Faculty Publications and Presentations

We construct finite element projectors that can be applied to functions with low regularity. These projectors are continuous in a weighted norm arising naturally when modeling devices with axial symmetry. They have important commuting diagram properties needed for finite element analysis. As an application, we use the projectors to prove quasioptimal convergence for the edge finite element approximation of the axisymmetric time-harmonic Maxwell equations on nonsmooth domains. Supplementary numerical investigations on convergence deterioration at high wavenumbers and near Maxwell eigenvalues and are also reported.

Parallel-Sparse Symmetrical/Unsymmetrical Finite Element Domain Decomposition Solver With Multi-Point Constraints For Structural/Acoustic Analysis, Siroj Tungkahotara, Willie R. Watson, Duc T. Nguyen, Subramaniam D. Rajan

Civil & Environmental Engineering Faculty Publications

Details of parallel-sparse Domain Decomposition (DD) with multi-point constraints (MPC) formulation are explained. Major computational components of the DD formulation are identified. Critical roles of parallel (direct) sparse and iterative solvers with MPC are discussed within the framework of DD formulation. Both symmetrical and unsymmetrical system of simultaneous linear equations (SLE) can be handled by the developed DD formulation. For symmetrical SLE, option for imposing MPC equations is also provided.

Large-scale (up to 25 million unknowns involving complex numbers) structural and acoustic Finite Element (FE) analysis are used to evaluate the parallel computational performance of the proposed DD implementation using …

The Convergence Of V-Cycle Multigrid Algorithms For Axisymmetric Laplace And Maxwell Equations, Jay Gopalakrishnan, Joseph E. Pasciak

Mathematics and Statistics Faculty Publications and Presentations

We investigate some simple finite element discretizations for the axisymmetric Laplace equation and the azimuthal component of the axisymmetric Maxwell equations as well as multigrid algorithms for these discretizations. Our analysis is targeted at simple model problems and our main result is that the standard V-cycle with point smoothing converges at a rate independent of the number of unknowns. This is contrary to suggestions in the existing literature that line relaxations and semicoarsening are needed in multigrid algorithms to overcome difficulties caused by the singularities in the axisymmetric Maxwell problems. Our multigrid analysis proceeds by applying the well known regularity …

Lattice Quantum Algorithm For The Schrodinger Wave Equation In 2+1 Dimensions With A Demonstration By Modeling Soliton Instabilities, Jeffrey Yepez, George Vahala, Linda L. Vahala

Electrical & Computer Engineering Faculty Publications

A lattice-based quantum algorithm is presented to model the non-linear Schrödinger-like equations in 2 + 1 dimensions. In this lattice-based model, using only 2 qubits per node, a sequence of unitary collide (qubit-qubit interaction) and stream (qubit translation) operators locally evolve a discrete field of probability amplitudes that in the long-wavelength limit accurately approximates a non-relativistic scalar wave function. The collision operator locally entangles pairs of qubits followed by a streaming operator that spreads the entanglement throughout the two dimensional lattice. The quantum algorithmic scheme employs a non-linear potential that is proportional to the moduli square of the wave function. …

Analysis Of A Multigrid Algorithm For Time Harmonic Maxwell Equations, Jay Gopalakrishnan, Joseph E. Pasciak, Leszek Demkowicz

Mathematics and Statistics Faculty Publications and Presentations

This paper considers a multigrid algorithm suitable for efficient solution of indefinite linear systems arising from finite element discretization of time harmonic Maxwell equations. In particular, a "backslash" multigrid cycle is proven to converge at rates independent of refinement level if certain indefinite block smoothers are used. The method of analysis involves comparing the multigrid error reduction operator with that of a related positive definite multigrid operator. This idea has previously been used in multigrid analysis of indefinite second order elliptic problems. However, the Maxwell application involves a nonelliptic indefinite operator. With the help of a few new estimates, the …

Upper Bounds To The Clique Width Of Graphs, Bruno Courcelle, Stephan Olariu

Computer Science Faculty Publications

Hierarchical decompositions of graphs are interesting for algorithmic purposes. Many NP complete problems have linear complexity on graphs with tree-decompositions of bounded width. We investigate alternate hierarchical decompositions that apply to wider classes of graphs and still enjoy good algorithmic properties. These decompositions are motivated and inspired by the study of vertex-replacement context-free graph grammars. The complexity measure of graphs associated with these decompositions is called clique width. In this paper we bound the clique width of a graph in terms of its tree width on the one hand, and of the clique width of its edge complement on …

Multigrid For The Mortar Finite Element Method, Jay Gopalakrishnan, Joseph E. Pasciak

Mathematics and Statistics Faculty Publications and Presentations

A multigrid technique for uniformly preconditioning linear systems arising from a mortar finite element discretization of second order elliptic boundary value problems is described and analyzed. These problems are posed on domains partitioned into subdomains, each of which is independently triangulated in a multilevel fashion. The multilevel mortar finite element spaces based on such triangulations (which need not align across subdomain interfaces) are in general not nested. Suitable grid transfer operators and smoothers are developed which lead to a variable Vcycle preconditioner resulting in a uniformly preconditioned algebraic system. Computational results illustrating the theory are also presented.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …