Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Decomposition of Dense Matrices over GF(2)
124
0
0.0
(
0
)
Added by
Martin Albrecht
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work we describe an efficient implementation of a hierarchy of algorithms for the decomposition of dense matrices over the field with two elements (GF(2)). Matrix decomposition is an essential building block for solving dense systems of linear and non-linear equations and thus much research has been devoted to improve the asymptotic complexity of such algorithms. In this work we discuss an implementation of both well-known and improved algorithms in the M4RI library. The focus of our discussion is on a new variant of the M4RI algorithm - denoted MMPF in this work -- which allows for considerable performance gains in practice when compared to the previously fastest implementation. We provide performance figures on x86_64 CPUs to demonstrate the viability of our approach.
rate research
Read More
We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (GF(2)). In particular we present our implementation -- in the M4RI library -- of Strassen-Winograd matrix multiplication and the Method of the Four Russians multiplication (M4RM) and compare it against other available implementations. Good performance is demonstrated on on AMDs Opteron and particulary good performance on Intels Core 2 Duo. The open-source M4RI library is available stand-alone as well as part of the Sage mathematics software. In machine terms, addition in GF(2) is logical-XOR, and multiplication is logical-AND, thus a machine word of 64-bits allows one to operate on 64 elements of GF(2) in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, element-wise operations over GF(2) are relatively cheap. In fact, in this paper, we conclude that the actual bottlenecks are memory reads and writes and issues of data locality. We present our empirical findings in relation to minimizing these and give an analysis thereof.
We introduce a consistent and efficient method to construct self-dual codes over $GF(q)$ with symmetric generator matrices from a self-dual code over $GF(q)$ of smaller length where $q equiv 1 pmod 4$. Using this method, we improve the best-known minimum weights of self-dual codes, which have not significantly improved for almost two decades. We focus on a class of self-dual codes, including double circulant codes. Using our method, called a `symmetric building-up construction, we obtain many new self-dual codes over $GF(13)$ and $GF(17)$ and improve the bounds of best-known minimum weights of self-dual codes of lengths up to 40. Besides, we compute the minimum weights of quadratic residue codes that were not known before. These are: a [20,10,10] QR self-dual code over $GF(23)$, two [24,12,12] QR self-dual codes over $GF(29)$ and $GF(41)$, and a [32,12,14] QR self-dual codes over $GF(19)$. They have the highest minimum weights so far.
Four recursive constructions of permutation polynomials over $gf(q^2)$ with those over $gf(q)$ are developed and applied to a few famous classes of permutation polynomials. They produce infinitely many new permutation polynomials over $gf(q^{2^ell})$ for any positive integer $ell$ with any given permutation polynomial over $gf(q)$. A generic construction of permutation polynomials over $gf(2^{2m})$ with o-polynomials over $gf(2^m)$ is also presented, and a number of new classes of permutation polynomials over $gf(2^{2m})$ are obtained.
Updating a linear least squares solution can be critical for near real-time signalprocessing applications. The Greville algorithm proposes a simple formula for updating the pseudoinverse of a matrix A $in$ R nxm with rank r. In this paper, we explicitly derive a similar formula by maintaining a general rank factorization, which we call rank-Greville. Based on this formula, we implemented a recursive least squares algorithm exploiting the rank-deficiency of A, achieving the update of the minimum-norm least-squares solution in O(mr) operations and, therefore, solving the linear least-squares problem from scratch in O(nmr) operations. We empirically confirmed that this algorithm displays a better asymptotic time complexity than LAPACK solvers for rank-deficient matrices. The numerical stability of rank-Greville was found to be comparable to Cholesky-based solvers. Nonetheless, our implementation supports exact numerical representations of rationals, due to its remarkable algebraic simplicity.
The orientation of the magnetic field (B-field) in the filamentary dark cloud GF 9 was traced from the periphery of the cloud into the L1082C dense core that contains the low-mass, low-luminosity Class 0 young stellar object (YSO) GF 9-2 (IRAS 20503+6006). This was done using SOFIA HAWC+ dust thermal emission polarimetry (TEP) at 216 um in combination with Mimir near-infrared background starlight polarimetry (BSP) conducted at H-band (1.6 um) and K-band (2.2 um). These observations were augmented with published I-band (0.77 um) BSP and Planck 850 um TEP to probe B-field orientations with offset from the YSO in a range spanning 6000 AU to 3 pc. No strong B-field orientation change with offset was found, indicating remarkable uniformity of the B-field from the cloud edge to the YSO environs. This finding disagrees with weak-field models of cloud core and YSO formation. The continuity of inferred B-field orientations for both TEP and BSP probes is strong evidence that both are sampling a common B-field that uniformly threads the cloud, core, and YSO region. Bayesian analysis of Gaia DR2 stars matched to the Mimir BSP stars finds a distance to GF 9 of 270 +/- 10 pc. No strong wavelength dependence of B-field orientation angle was found, contrary to previous claims.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
