Search results for "sparse"
showing 10 items of 75 documents
Unary Languages Recognized by Two-Way One-Counter Automata
2014
A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear–space Turing machines. We also show …
An Advanced Numerical Model in Solving Thin-Wire Integral Equations by Using Semi-Orthogonal Compactly Supported Spline Wavelets
2003
Abstract—In this paper, the semi-orthogonal compactly sup- ported spline wavelets are used as basis functions for the efficient solution of the thin-wire electric field integral equation (EFIE) in frequency domain. The method of moments (MoM) is used via the Galerkin procedure. Conventional MoM directly applied to the EFIE, leads to dense matrix which often becomes computation- ally intractable when large-scale problems are approached. To overcome these difficulties, wavelets can be used as a basis set so obtaining the generation of a sparse matrix; this is due to the local supports and the vanishing moments properties of the wavelets. In the paper, this technique is applied to analyze elec…
Assessment of computational methods for the analysis of single-cell ATAC-seq data
2019
Abstract Background Recent innovations in single-cell Assay for Transposase Accessible Chromatin using sequencing (scATAC-seq) enable profiling of the epigenetic landscape of thousands of individual cells. scATAC-seq data analysis presents unique methodological challenges. scATAC-seq experiments sample DNA, which, due to low copy numbers (diploid in humans), lead to inherent data sparsity (1–10% of peaks detected per cell) compared to transcriptomic (scRNA-seq) data (10–45% of expressed genes detected per cell). Such challenges in data generation emphasize the need for informative features to assess cell heterogeneity at the chromatin level. Results We present a benchmarking framework that …
Dual Extrapolation for Sparse Generalized Linear Models
2020
International audience; Generalized Linear Models (GLM) form a wide class of regression and classification models, where prediction is a function of a linear combination of the input variables. For statistical inference in high dimension, sparsity inducing regularizations have proven to be useful while offering statistical guarantees. However, solving the resulting optimization problems can be challenging: even for popular iterative algorithms such as coordinate descent, one needs to loop over a large number of variables. To mitigate this, techniques known as screening rules and working sets diminish the size of the optimization problem at hand, either by progressively removing variables, o…
Hardware-efficient matrix inversion algorithm for complex adaptive systems
2012
This work shows an FPGA implementation for the matrix inversion algebra operation. Usually, large matrix dimension is required for real-time signal processing applications, especially in case of complex adaptive systems. A hardware efficient matrix inversion procedure is described using QR decomposition of the original matrix and modified Gram-Schmidt method. This works attempts a direct VHDL description using few predefined packages and fixed point arithmetic for better optimization. New proposals for intermediate calculations are described, leading to efficient logic occupation together with better performance and accuracy in the vector space algebra. Results show that, for a relatively s…
Circular law for sparse random regular digraphs
2020
Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studyi…
Using the dglars Package to Estimate a Sparse Generalized Linear Model
2015
dglars is a publicly available R package that implements the method proposed in Augugliaro et al. (J. R. Statist. Soc. B 75(3), 471-498, 2013) developed to study the sparse structure of a generalized linear model (GLM). This method, called dgLARS, is based on a differential geometrical extension of the least angle regression method. The core of the dglars package consists of two algorithms implemented in Fortran 90 to efficiently compute the solution curve. dglars is a publicly available R package that implements the method proposed in Augugliaro et al. (J. R. Statist. Soc. B 75(3), 471-498, 2013) developed to study the sparse structure of a generalized linear model (GLM). This method, call…
Assessing the performance of thermal inertia and Hydrus models to estimate surface soil water content
2017
The knowledge of soil water content (SWC) dynamics in the upper soil layer is important for several hydrological processes. Due to the difficulty of assessing the spatial and temporal SWC dynamics in the field, some model-based approaches have been proposed during the last decade. The main objective of this work was to assess the performance of two approaches to estimate SWC in the upper soil layer under field conditions: the physically-based thermal inertia and the Hydrus model. Their validity was firstly assessed under controlled laboratory conditions. Thermal inertia was firstly validated in laboratory conditions using the transient line heat source (TLHS) method. Then, it was applied in…
A branch and bound algorithm for the matrix bandwidth minimization
2008
In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the propose…
LightSpMV: Faster CSR-based sparse matrix-vector multiplication on CUDA-enabled GPUs
2015
Compressed sparse row (CSR) is a frequently used format for sparse matrix storage. However, the state-of-the-art CSR-based sparse matrix-vector multiplication (SpMV) implementations on CUDA-enabled GPUs do not exhibit very high efficiency. This has motivated the development of some alternative storage formats for GPU computing. Unfortunately, these alternatives are incompatible with most CPU-centric programs and require dynamic conversion from CSR at runtime, thus incurring significant computational and storage overheads. We present LightSpMV, a novel CUDA-compatible SpMV algorithm using the standard CSR format, which achieves high speed by benefiting from the fine-grained dynamic distribut…