Search

The following two chapters will focus on the theory and application of linear regression models, which play a major role in statistics. We already studied some examples in Sect. 2.2. In addition to the direct application of linear regression models, they are also the basis of a variety of more complex regression methods.

In Chapter 7 the variational formulation has been introduced to prove the existence of a (weak) solution. Now it will turn out that the variational formulation is extremely important for numerical purposes. It establishes a new, very flexible discretisation method. After historical remarks in Section 8.1 we introduce the Ritz–Galerkin method in Section 8.2. The basic principle is the replacement of the function space V in the variational formulation by an N-dimensional space. This leads to a system of N linear equations (§8.2.1). As described in §8.2.2, the theory from Chapter 7 can be applied. In §8.2.3 two criteria, the inf-sup condition and V-ellipticity are described which are sufficient for solvability. §8.2.4 contains numerical examples. Error estimates are discussed in Section 8.3. The quasioptimality of the Ritz–Galerkin method proved in §8.3.1 shifts the discussion to the approximation properties of the subspace (§8.3.2). The finite elements introduced in Section 8.4 form a special finite-dimensional subspace offering many practical advantages. The corresponding error estimates are given in Section 8.5. Generalisations to differential equations of higher order and to non-polygonal domains are investigated in Section 8.6. An important practical subject are a-posteriori error estimates discussed in Section 8.7. When solving the arising system of linear equations, the properties of the system matrix is of interest which are investigated in Section 8.8. Several other topics are sketched in the final Section 8.9.

The problem discussed herein is the one of finding the set of stationary points for the Coulomb potential function $$ FP=\sum _{j=1}^K m_j / |PP_j | $$ for the cases of $$ K=3 $$ and $$ K=4 $$ positive charges $$ \{m_j\}_{j=1}^K $$ fixed at the positions $$ \{P_j\}_{j=1}^K \subset \mathbb R^2 $$. Our approach is based on reducing the problem to that of evaluation of the number of real solution of an appropriate algebraic system of equations. We also investigate the bifurcation picture in the parameter domains.

Censor-Hillel et al. [PODC’15] recently showed how to efficiently implement centralized algebraic algorithms for matrix multiplication in the congested clique model, a model of distributed computing that has received increasing attention in the past few years. This paper develops further algebraic techniques for designing algorithms in this model. We present deterministic and randomized algorithms, in the congested clique model, for efficiently computing multiple independent instances of matrix products, computing the determinant, the rank and the inverse of a matrix, and solving systems of linear equations. As applications of these techniques, we obtain more efficient algorithms for the computation, again in the congested clique model, of the all-pairs shortest paths and the diameter in directed and undirected graphs with small weights, improving over Censor-Hillel et al.’s work. We also obtain algorithms for several other graph-theoretic problems such as computing the number of edges in a maximum matching and the Gallai-Edmonds decomposition of a simple graph, and computing a minimum vertex cover of a bipartite graph.

So far, we have only occupied ourselves with continuous transformation groups, hence with groups which are represented by one system of equations of the form

If a system of equations remains invariant by all transformations of an \(r\)-term group \(X_1f,\dots , X_rf\), we say

We investigate the power of graph isomorphism algorithms based on algebraic reasoning techniques like Grobner basis computation. The idea of these algorithms is to encode two graphs into a system of equations that are satisfiable if and only if if the graphs are isomorphic, and then to (try to) decide satisfiability of the system using, for example, the Grobner basis algorithm. In some cases this can be done in polynomial time, in particular, if the equations admit a bounded degree refutation in an algebraic proof systems such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on the polynomial calculus degree over all fields of characteristic \(\ne 2\) and also linear lower bounds for the degree of Positivstellensatz calculus derivations.

For the stability analysis of linear time-invariant descriptor systems two different generalizations of the classical Lyapunov matrix equation are considered. The first generalization includes the singular matrix related to the time-derivatives of the descriptor variables in an obviously symmetric form; the second one shows at a first sight no symmetry which additionally has to be asked for explicitly. This second approach is well-known for ‘admissible’ descriptor systems which includes a restriction to systems of index k = 1. In this contribution the second approach will be generalized to systems with arbitrary index k ≥ 1. Both approaches will be compared with each other showing different solvability conditions and different solutions in general. But for the problem of analyzing asymptotic stability the solution behaviors of the two generalized Lyapunov matrix equations coincide. In spite of the different procedures both approaches lead to the same Lyapunov function for the analysis of asymptotic stability of linear time-invariant descriptor systems. The two approaches will be illustrated by the stability analysis of mechanical descriptor systems, i.e. by mechanical systems with holonomic constrains. Although the application of the approaches usually is very costly, they represent suitable tools for the stability analysis of linear time-invariant descriptor systems.

We develop an algorithm for the computation of a locally affine optical flow field as an extension of the Lucas-Kanade LK method. The classical LK method solves a system of linear equations assuming that the flow field is locally constant. Our method solves a collection of systems of linear equations assuming that the flow field is locally affine. Since our method combines the minimisation of the total variation and the decomposition of the region, the method is a local version of the $l_2^2$ -l 1 optical flow computation. Since the linearly diverging vector field from a point is locally affine, our method is suitable for optical flow computation for diverging image sequences such as front-view sequences observed by car-mounted cameras.

Simulations of a 2D unsteady turbulent boundary layer flow model with a quasi-simultaneous interaction method converge for attached and separated flow. The interaction method ensures that no singularity arises in the numerical system of equations. The singularity will occur if the interaction law coefficient is positive and higher in value than a critical value which depends on the applied flow model. An analysis of the eigenvalues of the system of equations proves this. A sign change in one of the eigenvalues causes the singularity and a proper value of the interaction law coefficient prevents this.

Many complex mathematical problems have a linear system of equations hidden in it. For example, to solve a nonlinear system of equations a linearization of the problem will lead to a sequence of linear systems. To give a command to solve a general linear system \(\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}\) in MATLAB is simple. Most often x=A∖b will do the trick. However, problems can occur. The matrix \(\boldsymbol{A}\) can be singular or almost singular and then the computed solution can be quite inaccurate. For a better understanding of when such problems can occur one needs some background in linear algebra.

An extension of the Rational Lanczos reduction method (RLANRM) to simulate efficiently surface-ground water interactions in models of conjunctive use systems is proposed. The RLANRM is used to form an orthogonal base of a Krylov’s reduction subspace. As a criterion to stop the generation of the reduction’s subspace, accumulated volumetric allocation factors of the Lanczos vectors are used. The reduction scheme is applied on the groundwater flow model to obtain a sequence of reduced systems of linear equations, whose solutions represent the states of the aquifer along the simulation horizon. To calculate the exchange volumes of water between the aquifer and the river during each simulation step, a discrete integration of the aquifer’s Lanczos states has been proposed. The concept of control parameters is also included on the RLANRM to accelerate the calculations of surface-ground water relations and other state variables.

Least-squares problems occur often in practice, for example, when a parametrized model is used to describe a behavior of a chemical, physical or an economic application. In this paper, we describe a method for solving least-squares problems that are given as a large system of equations. The solution combines the commonly used methods with algorithmic differentiation and shared-memory multiprocessing. The system of equations contains model functions that are independent from each other. This independence enables the usage of a multiprocessing approach. With help of algorithmic differentiation by source transformation, we obtain the derivative code of the residual function. The advantage of using source transformation is that we can transform the OpenMP pragmas of the input code into corresponding pendants in the derivative code. This is, in particular in the adjoint case, not a straightforward approach. We show the scaling properties of the derivative code and of the optimization process.

Linear system of equations is been used more and more widely in social life. Most people use the estimated value for a variety of computing that will cause a lot of errors. Familiar with a variety of ill-posed linear equations solution can make us grasp the algorithm and make the error reduce to the minimum in practice, thereby increasing the accuracy to reduce unnecessary trouble. The Ax = b calculation solution equivalent to solve the (A + E)x = b perturbation equations of floating point error analysis results shown. We choose algorithm to make the || E || as small as possible. In order to simplify the calculation, the perturbation matrix generally desirable as the simplest rank one type, this paper discusses the problem and gives a feasible algorithm.

In this paper, we analyze the potential of using weights for block-asynchronous relaxation methods on GPUs. For this purpose, we introduce different weighting techniques similar to those applied in block-smoothers for multigrid methods. For test matrices taken from the University of Florida Matrix Collection we report the convergence behavior and the total runtime for the different techniques. Analyzing the results, we observe that using weights may accelerate the convergence rate of block-asynchronous iteration considerably. While component-wise relaxation methods are seldom directly applied to systems of linear equations, using them as smoother in a multigrid framework they often provide an important contribution to finite element solvers. Since the parallelization potential of the classical smoothers like SOR and Gauss-Seidel is usually very limited, replacing them by weighted block-asynchronous smoothers may be beneficial to the overall multigrid performance. Due to the increase of heterogeneity in today's architecture designs, the significance and the need for highly parallel asynchronous smoothers is expected to grow.

An algorithm to solve the least square support vector machine (LSSVM) is presented. The underlying optimization problem for LSSVM follows a system of linear equations. The proposed algorithm incorporates a fuzzy c-mean (FCM) clustering approach and the application of a recurrent neural network (RNN) to solve the system of linear equations. First, a reduced training set is obtained by the FCM clustering approach and used to train LSSVM. Then a gradient system with discontinuous righthand side, interpreted as an RNN, is designed by using the corresponding system of linear equations. The fusion of FCM clustering approach and RNN overcomes the loss of spareness of LSSVM. The efficiency of the algorithm is empirically shown on a benchmark data set generated from the University of California at Irvine (UCI) machine learning database.

We present the first implementation of Newton’s method for solving systems of equations over ω-continuous semirings (based on [5,11]). For instance, such equation systems arise naturally in the analysis of interprocedural programs or the provenance computation for Datalog. Our implementation provides an attractive alternative for computing their exact least solution in some cases where the ascending chain condition is not met and hence, standard fixed-point iteration needs to be combined with some over-approximation (e.g., widening techniques) to terminate. We present a generic C++ library along with the main algorithms and analyze their complexity. Furthermore, we describe our implementation of the counting semiring based on semilinear sets. Finally, we discuss motivating examples as well as performance benchmarks.

The purpose of this paper is three-fold. First, we develop an algorith for the computation a locally affine optical flow field from multichannel images as an extension of the Lucus-Kanade LK method. The classical LK method solves a system of linear equations assuming that the flow field is locally constant. Our method solves a collection of systems of linear equations assuming the flow field is locally affine. For autonomous navigation in a real environment, the adaptation of the motion and image analysis algorithm to illumination changes is a fundamental problem, because illumination changes in an image sequence yield counterfeit obstacles. Second, we evaluate the colour channel selection of colour optical flow computation. By selecting an appropriate colour channel, it is possible to avoid these counterfeit obstacle regions in the snapshot image in front of a vehicle. Finally, we introduce an evaluation criterion for the computed optical flow field without ground truth.

In 1977 I finished my PhD Thesis on categories of stochastic machines. The main attention was paid on computing behavior, establishing equivalence of states and equivalence of stochastic machines, as well as on reduction and minimization. All these problems were solved for stochastic machines, using linear algebra: they require solving linear system of equations with traditional algebraic operations, establishing linear dependence or linear independence of vectors, Noetherian property. After 1980 I was interested in similar problems, but for finite fuzzy machines.

Surface approximation using splines has been widely used in geometric modeling and image analysis. One of the main problems associated with surface approximation by splines is the adequate selection of the number and location of the knots, as well as, the solution of the system of equations generated by tensor product spline surfaces. In this work, we use a hierarchical genetic algorithm (HGA) to tackle the B-spline surface approximation problem. The proposed approach is based on a novel hierarchical gene structure for the chromosomal representation, which allows us to determine the number and location of the knots for each surface dimension, and the B-spline coefficients simultaneously. Our approach is able to find solutions with fewest parameters within of the B-spline basis functions. The method is fully based on genetic algorithms and does not require subjective parameters like smooth factor or knot locations to perform the solution. In order to validate the efficacy of the proposed approach, simulation results from several tests on smooth surfaces have been included.

To solve numerically boundary value problems for parabolic equations with mixed derivatives, the construction of difference schemes with prescribed quality faces essential difficulties. In parabolic problems, some possibilities are associated with the transition to a new formulation of the problem, where the fluxes derivatives with respect to a spatial direction are treated as unknown quantities. In this case, the original problem is rewritten in the form of a boundary value problem for the system of equations in the fluxes. This work deals with studying schemes with weights for parabolic equations written in the flux coordinates. Unconditionally stable flux locally one-dimensional schemes of the first and second order of approximation in time are constructed for parabolic equations without mixed derivatives. A peculiarity of the system of equations written in flux variables for equations with mixed derivatives is that there do exist coupled terms with time derivatives.

A Method of optimization of circular plates of piece wise constant thickness is developed. The material of plates is assumed to be an ideal elastic plastic material which obeys a non-linear yield condition and associated flow law. The cases of plates made of homogeneous and unidirectionally reinforced composite materials are studied. It is assumed that the unidirectional composite can be considered as an orthotropic material which obeys non-linear Hill’s yield condition in the range of plastic deformations. Using the pure bending theory of thin plates, the stress strain state of the plate is determined for the initial elastic and subsequent elastic plastic stage of deformation. When deriving necessary optimality conditions with the aid of the control theory the method of the extended functional is employed. This results in a differential- algebraic system of equations. The latter is solved numerically. The effectivity of the design established is assessed numerically in the cases of two- and four-stepped plates.

In this paper an outline about the geometric concept of nonlinear electronic circuits is given. With this geometric concept the fast switching behavior of circuits, i.e. the jumps in their state space, is illustrated and a jump condition is formulated. Furthermore, the developed geometric approach is adapted to MNA based systems of equations. This new method enables the simulation of such ill-conditioned circuits without regularization and presents an implementation approach for common circuit simulators like SPICE.

In this chapter we treat the solution of systems of linear equations in finite dimension spaces. This can be seen as examples of inverse reconstruction problems of Type I.We present a mathematical analysis of these linear inverse problems of finite dimension based on the spectral theorem.We study several aspects and behaviour of well-established methods for solving inverse problems. In particular, the concept of regularization, a very important notion in the area of inverse problems, will be dealt with. The analysis presented here is elementary – it depends on notions of linear algebra and convergence of numerical series. A similar study of regularization for problems in infinite dimensional spaces depends on functional analysis and is beyond the scope of this book. The interested reader is encouraged to consult [44, 29].

Multiple rotation averaging is an important problem in computer vision. The problem is challenging because of the nonlinear constraints required to represent the set of rotations. To our knowledge no one has proposed any globally optimal solution for the case of simultaneous updates of the rotations. In this paper we propose a simple procedure based on Lagrangian duality that can be used to verify global optimality of a local solution, by solving a linear system of equations. We show experimentally on real and synthetic data that unless the noise levels are extremely high this procedure always generates the globally optimal solution.

Fuzzy k-means clustering algorithms have successfully been applied to digital image segmentations and classifications as an improvement of the conventional k-means cluster algorithm. The limitation of the Fuzzy k-means algorithm is its large computation cost. In this paper, we propose a Successive Over-Relaxation (SOR) based fuzzy k-means algorithm in order to accelerate the convergence of the algorithm. The SOR is a variant of the Gauss---Seidel method for solving a linear system of equations, resulting in faster convergence. The proposed method has been applied to classification of remotely sensed images. Experimental results show that the proposed SOR based fuzzy k-means algorithm can improve convergence speed significantly and yields comparable similar classification results with conventional fuzzy k-means algorithm.

In recent years, attention has been devoted to the development of efficient iterative solvers for the solution of the linear system of equations arising from the discontinuous Galerkin (DG) discretization of a range of model problems. In the framework of two level preconditioners, scalable non-overlapping Schwarz methods have been proposed and analyzed for the h–version of the DG method in the articles [1, 2, 6, 7, 9]. Recently, in [3] it has been proved that the non-overlapping Schwarz preconditioners can also be successfully employed to reduce the condition number of the stiffness matrices arising from a wide class of high–order DG discretizations of elliptic problems. In this article we aim to validate the theoretical results derived in [3] for the multiplicative Schwarz preconditioner and for its symmetrized variant by testing their numerical performance.

In an overdetermined and feasible system of linear equations Ax = b, let vector b be corrupted, in the way that at most k entries are off their true values. Assume that we can check in the restricted system given by any minimal dependent set of rows, the correctness of all corresponding values in b. Furthermore, A has only coefficients 0 and 1, with at most two 1s in each row. We wish to recover the correct values in b and x as much as possible. The problem arises in a certain chemical mixture inference application in molecular biology, where every observable reaction product stems from at most two candidate substances. After formalization we prove that the problem is NP-hard but fixed-parameter tractable in k. The FPT result relies on the small girth of certain graphs.

The current microprocessors are concentrating on the multiprocessor or multi-core system architecture. The parallel algorithms are recently focusing on multi-core system to take full utilization of multiple processors available in the system. The design of parallel algorithm and performance measurement is the major issue on today’s multi-core environment. Numerical problems arise in almost every branch of science which requires fast solution. System of linear equations has applications in fusion energy, structural engineering, ocean modeling and method of moment formulation. In this paper parallel algorithms for computing the solution of system of linear equations and approximate value of π are presented. The parallel performance of numerical algorithms on multicore system have been analyzed and presented. The experimental results reveal that the performances of parallel algorithms are better than sequential. We implemented the parallel algorithms using multithreading features of OpenMP.

Shape-from-Shading and photometric stereo are two fundamental problems in Computer Vision aimed at reconstructing surface depth given either a single image taken under a known light source or multiple images taken under different illuminations, respectively. Whereas the former utilizes partial differential equation (PDE) techniques to solve the image irradiance equation, the latter can be expressed as a linear system of equations in surface derivatives when 3 or more images are given. It therefore seems that current photometric stereo techniques do not extract all possible depth information from each image by itself. This paper utilizes PDE techniques for the solution of the combined Shape-from-Shading and photometric stereo problem when only 2 images are available. Extending our previous results on this problem, we consider the more realistic perspective projection of surfaces during the photographic process. Under these assumptions, there is a unique weak (Lipschitz continuous) solution to the problem at hand, solving the well known convex/concave ambiguity of the Shape-from-Shading problem. We propose two approximation schemes for the numerical solution of this problem, an up-wind finite difference scheme and a Semi-Lagrangian scheme, and analyze their properties. We show that both schemes converge linearly and accurately reconstruct the original surfaces. In comparison with a similar method for the orthographic 2-image photometric stereo, the proposed perspective one outperforms the orthographic one. We also demonstrate the method on real-life images. Our results thus show that using methodologies common in the field of Shape-from-Shading it is possible to recover more depth information for the photometric stereo problem under the more realistic perspective projection assumption.

Place invariants are the most important analysis technique for system nets. They take advantage of the constant effect of transitions: each time a transition t occurs in the mode β, the same multisets aremoved. The effect of (t, β) is linear. For instance, if the places in • t hold twice as many tokens, then t may occur twice as many times. The mathematics for linear behaviors is the well-known linear algebra with vectors, matrices and systems of equations. In fact, many aspects of Petri nets can be represented and calculated with these structures. We start with linear-algebraic notation for elementary system nets.

Linear model predictive control (MPC) assumes a linear system model, linear inequality constraints and a convex quadratic cost function. Thus, it can be formulated as a quadratic programming (QP) problem. Due to associated computational complexity of QP solving algorithms, its applicability is restricted to relatively slow dynamic systems. This paper presents an interior-point method (IPM) based QP solver for the solution of optimal control problem in MPC. We propose LU factorization to solve the system of linear equations efficiently at each iteration of IPM, which renders faster execution of MPC. The approach is demonstrated practically by applying MPC to QET DC Servomotor for position control application.

We present hybrid finite element methods for the Helmholtz equation and the time harmonic Maxwell equations, which allow us to reduce the unknowns to degrees of freedom supported only on the element facets and to use efficient iterative solvers for the resulting system of equations. For solving this system, additive and multiplicative Schwarz preconditioners with local smoothers and a domain decomposition preconditioner with an exact subdomain solver are presented. Good convergence properties of these preconditioners are shown by numerical experiments.

In this paper, we proposed a parallel hardware methodology employing the modified Gaussian elimination algorithm to efficiently solve linear system of equations (LSEs). Two parallel operators are issued in the hardware-optimized algorithm. Moreover, to be the proof-of-concept, the proposed parallel methodology is implemented to hardware structures in cases to address solving LSEs over GF(2) (primarily are bits operation) and LSEs with floating-point (IEEE-754 standard, 32-bit single precision) coefficient matrix. The corresponding hardware is mainly composed of uniformly distributed basic cells which store and register data, yielding a standalone worst case time complexity O(n 2) opposed to O(n 3) of the software replication. Finally, the given experimental result inosculated with the theory analysis.

In the paper we define the Dawson-Watanabe type superprocesses in random environment as solutions to the related martingale problems. An environment is modelled by a finite state time homogeneous Markov process with the given transition probability intensity matrix. A system of nonlinear stochastic equations is derived for a posteriori probabilities. Reduced system of linear equations is also obtained.

In this paper we discuss simulation techniques for a rising bubble in viscoelastic fluids via numerical methods based on high order FEM. A level set approach based on the work in (Sethian, Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and material science, 2nd edn. Cambridge University Press, 1999) is used for interface tracking between the bubble and the surrounding fluid. The two matters obey the Newtonian and the Oldroyd-B constitutive law in the case of a viscoelastic fluid while the flow model is given by the Navier-Stokes equations. The total system of equations is discretized in space by the LBB-stable finite element Q 2 P 1, and in time by the family of θ-scheme integrators. The solver is based on Newton-multigrid techniques (Damanik et al., J Comput Phys 228:3869–3881, 2009; J Non-Newton Fluid Mech 165:1105–1113, 2010) for nonlinear fluids. First, we validate the multiphase flow results with respect to the benchmark results in (Hysing et al., Int J Numer Methods Fluids 60(11):1259–1288, 2009), then we perform numerical simulations of a bubble rising in a viscoelastic fluid and show cusp formation at the trailing edge.

The modeling of physical phenomena in a variety of fields of scientific interest lead to a formulation in terms of partial differential equations. Especially when complex geometries as the domain of definition are involved, a direct and exact solution is not accessible, but numerical schemes are used to compute an approximate discrete solution. In this report, we focus on elliptic and parabolic types of equations that include spatial operators of second order. When discretizing such problems using commonly known discretization schemes such as finite element methods or finite volume methods, large systems of linear equations arise naturally. Their solution takes the largest amount of the overall computing time.

We give a brief overview of a formulation of the equations of general relativistic hydrodynamics, and one method for their numerical solution. The system of equations can be cast as first-order, hyperbolic system of conservation laws, following a explicit choice of an Eulerian observer and suitable vector of variables. We also present a brief overview of the numerical techniques used to solve this equation, providing an example of their applicability in one scenario of relativistic astrophysics namely, the quasi periodic oscillations of a thick accretion disk.

The procedure for the analysis of a load-bearing structure will be introduced in this chapter. Structures will be considered, which consist of multiple elements and are connected with each other on coupling points. The structure is supported properly and subjected with loads. Unknown are the deformations of the structure and the reaction forces at the supports. Furthermore, the internal reactions of the single element are of interest. The stiffness relation of the single elements are already known from the previous chapters. A global stiffness relation forms on the basis of these single stiffness relations. From a mathematical point of view the evaluation of the global stiffness relation equals the solving of a linear system of equations. As examples plane and general three-dimensional structures of bars and beams will be introduced.

In Chap. 6, on superlinear systems of Hammerstein integral equations and applications, we use the Leray–Schauder degree to obtain new results on the existence of solutions, and apply them to two-point boundary problems of systems of equations. We also are concerned with the existence of (component-wise) positive solutions for a semilinear elliptic system, where the nonlinear term is superlinear in one equation and sublinear in the other equation. By constructing a cone K 1×K 2, which is the Cartesian product of two cones in the space \(C(\overline{\Omega})\), and computing the fixed point index in K 1×K 2, we establish the existence of positive solutions for the system.

The determination of the particle distribution given the measured voltages in the receive coils is an inverse problem that is usually referred to as reconstruction. As it has already been discussed in Chap. 4, the relation between both quantities can be described by a linear integral equation. After discretization of time and space, a linear system of equations is obtained (see (4.44)).

The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem for random selection and study its complexity. Given L secret linear functions $f_1,\ldots,f_L:\mbox{\{0,1\}}^n\longrightarrow\mbox{\{0,1\}}^a$ , $RandomSelect\left(L,n,a\right)$ denotes the problem of learning f1 ,…,fL from values $\left(u,f_l\left(u\right)\right)$ , where the secret indices l∈{1,…,L} and the inputs $u\in\mbox{$\{0,1\}^n$}$ are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over $O\left(n^L\right)$ unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.

It was recently proved in [27] that all rational hypocycloids and epicycloids are Pythagorean hodograph curves, i.e., rational curves with rational offsets. In this paper, we extend the discussion to a more general class of curves represented by trigonometric polynomial support functions. We show that these curves are offsets to translated convolutions of scaled and rotated hypocycloids and epicycloids. Using this result, we formulate a new and very simple G 2 Hermite interpolation algorithm based on solving a small system of linear equations. The efficiency of the designed method is then presented on several examples. In particular, we show how to approximate general trochoids, which, as we prove, are not Pythagorean hodograph curves in general.

The nonlinear filter generator (NLFG) is a powerful building block commonly used in stream ciphers. In this paper, we present the direct sum decomposition of the NLFG output sequence that leads to a system of linear equations in the initial state of the NLFG and further to an efficient algebraic attack. The coefficients of the equation system rely only on the NLFG structure. The attack is operated in an online/offline manner, doing most of the work (determining the coefficients of the equation system) in the offline phase. Thus the online phase is very fast, requiring only four multiplications and one diagonalization of n×n matrices. Compared with related works, our attack has the advantages in both online computation cost and success probability. On the one hand, far fewer output bits and significantly less matrix computation are required in our attack, although the online computation complexity O(LC) (LC is the linear complexity of the output sequence) is the same as in the known Ronjom-Helleseth attack. On the other hand, the success probability of the attack is analyzed in this paper, different from most prior work. The success probability of this algebraic attack is $1-2^{-\phi(2^n-1)}$ (φ(·) is the Euler function), which is much greater than 1−2−n, the success probability of the Ronjom-Helleseth attack.

Grobner Bases [Buc70] and Cylindrical Algebraic Decomposition [Col75,CMMXY09] are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Grobner bases to the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.

The focus of this paper is on the analysis of the Conjugate Gradient method applied to a non-symmetric system of linear equations, arising from a Fast Fourier Transform-based homogenization method due to Moulinec and Suquet [1]. Convergence of the method is proven by exploiting a certain projection operator reflecting physics of the underlying problem. These results are supported by a numerical example, demonstrating significant improvement of the Conjugate Gradient-based scheme over the original Moulinec-Suquet algorithm.