Mathematics Commons^™

Asteroidal Sets And Dominating Targets In Graphs, Oleksiy Al-Saadi

Department of Computer Science and Engineering: Dissertations, Theses, and Student Research

The focus of this PhD thesis is on various distance and domination properties in graphs. In particular, we prove strong results about the interactions between asteroidal sets and dominating targets. Our results add to or extend a plethora of results on these properties within the literature. We define the class of strict dominating pair graphs and show structural and algorithmic properties of this class. Notably, we prove that such graphs have diameter 3, 4, or contain an asteroidal quadruple. Then, we design an algorithm to to efficiently recognize chordal hereditary dominating pair graphs. We provide new results that describe the …

Algorithmic Design And Computational Modeling Using Dynamic Spectrum Allocation Techniques To Optimize Bandwidth Management In Wireless Communication Systems, Ankit Walishetti

Distinguished Student Work

This study aims to address the pressing need for efficient spectrum management methodologies in wireless communication systems by developing innovative sorting and allocation algorithms. Leveraging Dynamic Spectrum Allocation (DSA) techniques, this research devises strategies to optimize the utilization of bandwidth within existing spectrum space, ultimately reducing the need for network infrastructure expansion.

Ensuring thorough coverage of DSA techniques, 5 distinct transmitter sorting algorithms were programmed and tested across 8 performance metrics designed to measure specific capabilities. For consistency, a single bandwidth allocation program was designed to ‘pack’ transmitters starting from the left endpoint of the spectrum space. Progressively varying the …

Persistent Relative Homology For Topological Data Analysis, Christian J. Lentz

Mathematics, Statistics, and Computer Science Honors Projects

A central problem in data-driven scientific inquiry is how to interpret structure in noisy, high-dimensional data. Topological data analysis (TDA) provides a solution via the language of persistent homology, which encodes features of interest as holes within a filtration of the data. The recently presented U-Match Decomposition places the standard persistence computation in a flexible form, allowing for straight-forward extensions of the algorithm to variations of persistent homology. We describe U-Match Decomposition in the context of persistent homology, and extend it to an algorithm for persistent relative homology, providing proofs for the correctness and stability of the presented algorithm.

Awegnn: Auto-Parametrized Weighted Element-Specific Graph Neural Networks For Molecules., Timothy Szocinski, Duc Duy Nguyen, Guo-Wei Wei

Mathematics Faculty Publications

While automated feature extraction has had tremendous success in many deep learning algorithms for image analysis and natural language processing, it does not work well for data involving complex internal structures, such as molecules. Data representations via advanced mathematics, including algebraic topology, differential geometry, and graph theory, have demonstrated superiority in a variety of biomolecular applications, however, their performance is often dependent on manual parametrization. This work introduces the auto-parametrized weighted element-specific graph neural network, dubbed AweGNN, to overcome the obstacle of this tedious parametrization process while also being a suitable technique for automated feature extraction on these internally complex …

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 …

New Characterizations Of Reproducing Kernel Hilbert Spaces And Applications To Metric Geometry, Daniel Alpay, Palle E. T. Jorgensen

Mathematics, Physics, and Computer Science Faculty Articles and Research

We give two new global and algorithmic constructions of the reproducing kernel Hilbert space associated to a positive definite kernel. We further present a general positive definite kernel setting using bilinear forms, and we provide new examples. Our results cover the case of measurable positive definite kernels, and we give applications to both stochastic analysis and metric geometry and provide a number of examples.

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 …

Strategies And Algorithms Of Sudoku, Callie Weaver

Mathematics Senior Capstone Papers

This paper discusses different strategies for the game of Sudoku and how those strategies relate to other problem solving techniques while also attempting to use those other techniques in a way that improves the strategies for Sudoku. This includes a thorough analysis of the general algorithm and an algorithm that is formed by the Occupancy Theorem and Preemptive Sets. This paper also compares these algorithms that directly relate to Sudoku with algorithms to similar combinatorial problems such as the Traveling Salesman problem and more. With the study of game theory becoming more popular, these strategies have also been shown to …

Towards A Novel Generalized Chinese Remainder Algorithm For Extended Rabin Cryptosystem, Justin Zhan, Peter J. Shiue, Shen C. Huang, Benjamin J. Lowe

Mathematical Sciences Faculty Research

This paper proposes a number of theorems and algorithms for the Chinese Remainder Theorem, which is used to solve a system of linear congruences, and the extended Rabin cryptosystem, which accepts a key composed of an arbitrary finite number of distinct primes. This paper further proposes methods to relax the condition on the primes with trade-offs in the time complexity. The proposed algorithms can be used to provide ciphertext indistinguishability. Finally, this paper conducts extensive experimental analysis on six large data sets. The experimental results show that the proposed algorithms are asymptotically tight to the existing decryption algorithm in the …

Graph Pebbling Algorithms And Lemke Graphs, Charles A. Cusack, Aaron Green, Airat Bekmetjev, Mark Powers

Faculty Publications

Given a simple, connected graph, a pebbling configuration (or just configuration) is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r. A configuration is solvable if every vertex is reachable. The pebbling number π(G) of a graph G is the minimum integer such that every configuration of size π(G) on G …

Do Men Matter? In Statistics, Probably, Michael Kelly

WWU Honors College Senior Projects

In statistical genetics, there are several parameters of a dataset which a researcher might, but which are difficult to estimate in practice. In this paper, we will be focusing on allele frequencies, null alleles, inbreeding coefficients and, to a certain extent, beta values. A common technique for obtaining these values, developed by Amy Anderson and her co-workers, is to jointly estimate all of them using an EM-algorithm and the method of maximum likelihood. Despite this technique being effective in general, it is currently unable to deal with males at X-linked markers. The purpose of this project is to modify the …

Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke

Honors Theses

In this thesis, Pascal's Triangle modulo n will be explored for n prime and n a prime power. Using the results from the case when n is prime, a novel proof of Lucas' Theorem is given. Additionally, using both the results from the exploration of Pascal's Triangle here, as well as previous results, an efficient algorithm for computation of binomial coefficients modulo n (a choose b mod n) is described, and its time complexity is analyzed and compared to naive methods. In particular, the efficient algorithm runs in O(n log(a)) time (as opposed to …

Cox Processes For Counting By Detection, Purnima Rajan, Yongming Ma, Bruno Jedynak

Portland Institute for Computational Science Publications

In this work, doubly stochastic Poisson (Cox) processes and convolutional neural net (CNN) classifiers are used to estimate the number of instances of an object in an image. Poisson processes are well suited to model events that occur randomly in space, such as the location of objects in an image or the enumeration of objects in a scene. The proposed algorithm selects a subset of bounding boxes in the image domain, then queries them for the presence of the object of interest by running a pre-trained CNN classifier. The resulting observations are then aggregated, and a posterior distribution over the …

Gaussian Processes With Context-Supported Priors For Active Object Localization, Bruno Jedynak

Portland Institute for Computational Science Publications

We devise an algorithm using a Bayesian optimization framework in conjunction with contextual visual data for the efficient localization of objects in still images. Recent research has demonstrated substantial progress in object localization and related tasks for computer vision. However, many current state-of-the-art object localization procedures still suffer from inaccuracy and inefficiency, in addition to failing to provide a principled and interpretable system amenable to high-level vision tasks. We address these issues with the current research.

Our method encompasses an active search procedure that uses contextual data to generate initial bounding-box proposals for a target object. We train a convolutional …

Incorporating A Spatial Prior Into Nonlinear D-Bar Eit Imaging For Complex Admittivities, Sarah J. Hamilton, Jennifer L. Mueller, Melody Alsaker

Mathematics, Statistics and Computer Science Faculty Research and Publications

Electrical Impedance Tomography (EIT) aims to recover the internal conductivity and permittivity distributions of a body from electrical measurements taken on electrodes on the surface of the body. The reconstruction task is a severely ill-posed nonlinear inverse problem that is highly sensitive to measurement noise and modeling errors. Regularized D-bar methods have shown great promise in producing noise-robust algorithms by employing a low-pass filtering of nonlinear (nonphysical) Fourier transform data specific to the EIT problem. Including prior data with the approximate locations of major organ boundaries in the scattering transform provides a means of extending the radius of the low-pass …

A Feature Selection Algorithm To Compute Gene Centric Methylation From Probe Level Methylation Data, Brittany Baur, Serdar Bozdag

Mathematics, Statistics and Computer Science Faculty Research and Publications

DNA methylation is an important epigenetic event that effects gene expression during development and various diseases such as cancer. Understanding the mechanism of action of DNA methylation is important for downstream analysis. In the Illumina Infinium HumanMethylation 450K array, there are tens of probes associated with each gene. Given methylation intensities of all these probes, it is necessary to compute which of these probes are most representative of the gene centric methylation level. In this study, we developed a feature selection algorithm based on sequential forward selection that utilized different classification methods to compute gene centric DNA methylation using probe …

The Log-Exponential Smoothing Technique And Nesterov’S Accelerated Gradient Method For Generalized Sylvester Problems, N. T. An, Daniel J. Giles, Nguyen Mau Nam, R. Blake Rector

Mathematics and Statistics Faculty Publications and Presentations

The Sylvester or smallest enclosing circle problem involves finding the smallest circle enclosing a finite number of points in the plane. We consider generalized versions of the Sylvester problem in which the points are replaced by sets. Based on the log-exponential smoothing technique and Nesterov’s accelerated gradient method, we present an effective numerical algorithm for solving these problems.

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.

Direct Eit Reconstructions Of Complex Admittivities On A Chest-Shaped Domain In 2-D, Sarah J. Hamilton, Jennifer L. Mueller

Mathematics, Statistics and Computer Science Faculty Research and Publications

Electrical impedance tomography (EIT) is a medical imaging technique in which current is applied on electrodes on the surface of the body, the resulting voltage is measured, and an inverse problem is solved to recover the conductivity and/or permittivity in the interior. Images are then formed from the reconstructed conductivity and permittivity distributions. In the 2-D geometry, EIT is clinically useful for chest imaging. In this work, an implementation of a D-bar method for complex admittivities on a general 2-D domain is presented. In particular, reconstructions are computed on a chest-shaped domain for several realistic phantoms including a simulated pneumothorax, …

Measures Of Centrality Based On The Spectrum Of The Laplacian, Scott D. Pauls, Daniel Remondini

Dartmouth Scholarship

We introduce a family of new centralities, the k-spectral centralities. k-Spectral centrality is a measurement of importance with respect to the deformation of the graph Laplacian associated with the graph. Due to this connection, k-spectral centralities have various interpretations in terms of spectrally determined information.

We explore this centrality in the context of several examples. While for sparse unweighted net- works 1-spectral centrality behaves similarly to other standard centralities, for dense weighted net- works they show different properties. In summary, the k-spectral centralities provide a novel and useful measurement of relevance (for single network elements as well as whole subnetworks) …

Convergence Analysis Of A Multigrid Algorithm For The Acoustic Single Layer Equation, Simon Gemmrich, Jay Gopalakrishnan, Nilima Nigam

Mathematics and Statistics Faculty Publications and Presentations

We present and analyze a multigrid algorithm for the acoustic single layer equation in two dimensions. The boundary element formulation of the equation is based on piecewise constant test functions and we make use of a weak inner product in the multigrid scheme as proposed in Bramble et al. (1994) . A full error analysis of the algorithm is presented. We also conduct a numerical study of the effect of the weak inner product on the oscillatory behavior of the eigenfunctions for the Laplace single layer operator.

On The Hardness Of Counting And Sampling Center Strings, Christina Boucher, Mohamed Omar

All HMC Faculty Publications and Research

Given a set S of n strings, each of length ℓ, and a nonnegative value d, we define a center string as a string of length ` that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of center strings for a given set of strings S and input parameters n, ℓ, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, ℓ, or d is fixed leads to …

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.

Information-Preserving Structures: A General Framework For Quantum Zero-Error Information, Robin Blume-Kohout, Hui Khoon Ng, David Poulin, Lorenza Viola

Dartmouth Scholarship

Quantum systems carry information. Quantum theory supports at least two distinct kinds of information (classical and quantum), and a variety of different ways to encode and preserve information in physical systems. A system’s ability to carry information is constrained and defined by the noise in its dynamics. This paper introduces an operational framework, using information-preserving structures, to classify all the kinds of information that can be perfectly (i.e., with zero error) preserved by quantum dynamics. We prove that every perfectly preserved code has the same structure as a matrix algebra, and that preserved information can always be corrected. We …

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 …