A Storage-Efficient Algorithm for Finding the Regularized Solution of a Large, Inconsistent System of Equations

We propose an algorithm which for any real number r, any k ?l matrix M and any k-vector y, finds the l-vector x which minimizes||x||² – r²||Mx – y||², i.e. it finds the "regularized"solution to the equation Mx = y. (|| || denotes the 2-norm.)The algorithm is iterative with the following properties: (i)in a single step it needs access to only one row of the matrixM, (ii) it needs to store only the present estimate of the solution(size l) and a "residual vector" of size k, (iii) in a singlestep it updates only one component of the residual vector. Becauseof these properties the algorithm has been found useful in "solving"very large inconsistent systems of equations. Convergence ofthe algorithm to the desired solution is proved and the rateof convergence of the algorithm is illustrated. The algorithmis considered here, not because it is believed to be generallysuperior to more commonly used iterative methods, but becausefor certain very large problems it may be the only feasiblemethod from the point of view of storage requirements.     

A Fast Direct Method for the Least Squares Solution of Slightly Overdetermined Sets of Linear Equations

Noble (1969) has described a method for the solution of N+Mlinear equations in N unknowns, which is based on an initialpartitioning of the matrix A, and which requires only the solutionof square sets of equations. He assumed rank (A) = N. We describehere an efficient implementation of Noble's method, and showthat it generalizes in a simple way to cover also rank deficientproblems. In the common case that the equation is only slightlyoverdetermined (M << N) the resulting algorithm is muchfaster than the standard methods based on M.G.S. or Householderreduction of A, or on the normal equations, and has a very similaroperation count to the algorithm of Cline (1973). Slightly overdetermined systems arise from Galerkin methodsfor non-Hermitian partial differential equations. In these systems,rank (A) = N and advantage can be taken of the structure ofthe matrix A to yield a least squares solution in (N²) operations.     

Inversion of Toeplitz Matrices which are not Strongly Non-singular

A type of patterned matrix called r-Toeplitz is introduced.This is more general than a block Toeplitz matrix, which resultswhen the order n of the matrix is a multiple of r.A well-knownalgorithm for inverting Toeplitz matrices is extended to dealwith r-Toeplitz matrices, involving O(rn²) operations.This enablesan algorithm to be produced for inverting Toeplitz matriceswhich are not strongly non-singular, when the standard techniquesbreak down.     

The Fast Numerical Solution of Very Large Elliptic Difference Schemes

Let L_kv_k = g_k be a system of difference equations discretizingan elliptic boundary value problem. Assume the system to be"very large", that means that the number of unknowns exceedsthe capacity of storage. We present a method for solving theproblem with much less storage requirement. For two-dimensionalproblems the size of the needed storage decreases from O(h^–2)to (or even O(h^–5/4)). The computational work increasesonly by a factor about six. The technique can be generalizedto nonlinear problems. The algorithm is also useful for computerswith a small number of parallel processors.     

Construction of Euclidian Monopoles

This paper describes a procedure for the construction of monopoleson three-dimensional Euclidean space, starting from their rationalmaps. A companion paper, ‘Euclidean monopoles and rationalmaps’, to appear in the same journal, describes the assignmentto a monopole of a rational map, from CP¹ to a suitable flagmanifold. In describing the reverse direction, this paper completesthe proof of the main theorem therein. A construction of monopoles from solutions to Nahm's equations(a system of ordinary differential equations) has been well-knownfor certain gauge groups for some time. These solutions arehard to construct however, and the equations themselves becomeincreasingly unwieldy when the gauge group is not SU(2). Here, in contrast, a rational map is the only initial data.But whereas one can be reasonably explicit in moving from Nahmdata to a monopole, here the monopole is only obtained fromthe rational map after solving a partial differential equation. A non-linear flow equation, essentially just the path of steepestdescent down the Yang-Mills-Higgs functional, is set up. Itis shown that, starting from an ‘approximate monopole’- constructed explicitly from the rational map - a solutionto the flow must exist, and converge to an exact monopole havingthe desired rational map. 1991 Mathematics Subject Classification:53C07, 53C80, 58D27, 58E15, 58G11.     

Two Diophantine Birds with One Stone

Integer Solutions are found to the equations t²–3(a²,b², (a + b)², (a–b)²) = p², q², r², s². These lead surprisinglyto solutions to the equations u² + (c², d², (c + d)², (c –d)²) = p², q², v², w², with the same values of p and q.     

Displacement structure approach to Cauchy and Cauchy–Vandermonde matrices: inversion formulas and fast algorithms

The confluent Cauchy and Cauchy–Vandermonde matrices are considered, which were studied earlier by various authors in different ways. In this paper, we use another way called displacement structure approach to deal with matrices of this kind. We show that the Cauchy and Cauchy–Vandermonde matrices satisfy some special type of matrix equations. This leads quite naturally to the inversion formulas and fast algorithms for matrices of this kind.     

On the computation of the generalized inverse of a polynomial matrix

The main purpose of this paper is to present a quicker and less memory-expensive algorithm for the generalized inversionof polynomial matrices than those presented earlier (Karampetakis,1997a Computation of the generalized inverse of a polynomialmatrix and applications. Linear Algebr. Appl. 252, 35–60 and Karampetakis, 1997b Generalized inverses of two variable polynomial matrices and applications. Circuit Syst. & Signal Process. 16, 439–453). Received 24 January, 1999. ⁺ karampetakis@ccf.auth.gr     

Updating and downdating an upper trapezoidal sparse orthogonal factorization{dagger}

^** Email: santos{at}ctima.uma.es^*** Corresponding Author. Email: pablito{at}ctima.uma.es We describe how to update and downdate an upper trapezoidalsparse orthogonal factorization, namely the sparse QR factorizationof A_k^T, where A_k is a ‘tall and thin’ full columnrank matrix formed with a subset of the columns of a fixed matrixA. In order to do this, we have adapted Saunders' techniquesof the early 1970s for square matrices, to rectangular matrices(with fewer columns than rows) by using the static data structureof George and Heath of the early 1980s but allowing row downdatingon it. An implicitly determined column permutation allows usto dispense with computing a new ordering after each update/downdate;it fits well into the LINPACK downdating algorithm and ensuresthat the updated trapezoidal factor will remain sparse. We giveall the necessary formulae even if the orthogonal factor isnot available, and we comment on our implementation using thesparse toolbox of MATLAB 5.     

Khayyam with Cabri: experiences of pre-service mathematics teachers with Khayyam's solution of cubic equations in dynamic geometry environment

The study reported in this article deals with the observed actionsof Turkish pre-service mathematics teachers in dynamic geometryenvironment (DGE) as they were learning Khayyam's method forsolving cubic equations formed as x³ + ax = b. Having learnedthe method, modelled it in DGE and verified the correctnessof the solution, students generated their own methods for solvingdifferent types of cubic equations such as x³ + ax² = b andx³ + a = bx in the light of Khayyam's method. With the presentedteaching experiment, students realized that Khayyam's mathematicsis different from theirs. We consider that this gave them anopportunity to have an insight about the cultural and socialaspects of mathematics. In addition, the teaching experimentshowed that dynamic geometry software is an excellent tool fordoing mathematics because of their dynamic nature and accurateconstructions. And, it can be easily concluded that the historyof mathematics is useful resource for enriching mathematicslearning environment.     

Multiplicative groups used for coding QAM signals

Recently, some multiplicative groups of algebraic integers wereused to obtain quadrature amplitude modulation (QAM) signalspaces and to design error-correcting codes. This paper showsthat one subgroup of the multiplicative group of units in thealgebraic integer ring of each quadratic number field with uniquefactorization property Q(m), modulo the ideal (2ⁿ), can be usedto obtain a QAM signal space of 2^2n–2 points with goodgeometrical properties, where n 3, m 1 (mod 8) and m is asquare-free rational integer. These QAM signals can be codedsuch that a differentially coherent method can be applied todemodulate the QAM signals. The multiplicative subgroups canalso be used to construct block codes over Gaussian integerswhich are able to correct some error patterns.     

Deformation Theory and The Computation of Zeta Functions

We present a new approach to the problem of computing the zetafunction of a hypersurface over a finite field. For a hypersurfacedefined by a polynomial of degree d in n variables over thefield of q elements, one desires an algorithm whose runningtime is a polynomial function of dⁿ log(q). (Here we assumed 2, for otherwise the problem is easy.) The case n = 1 isrelated to univariate polynomial factorisation and is comparativelystraightforward. When n = 2 one is counting points on curves,and the method of Schoof and Pila yields a complexity of , where the function C_d depends exponentiallyon d. For arbitrary n, the theorem of the author and Wan givesa complexity which is a polynomial function of (pdⁿ log(q))ⁿ,where p is the characteristic of the field. A complexity estimateof this form can also be achieved for smooth hypersurfaces usingthe method of Kedlaya, although this has only been worked outin full for curves. The new approach we present should yielda complexity which is a small polynomial function of pdⁿ log(q).In this paper, we work this out in full for Artin–Schreierhypersurfaces defined by equations of the form Z^p – Z= f, where the polynomial f has a diagonal leading form. Themethod utilises a relative p-adic cohomology theory for familiesof hypersurfaces, due in essence to Dwork. As a corollary ofour main theorem, we obtain the following curious result. Letf be a multivariate polynomial with integer coefficients whoseleading form is diagonal. There exists an explicit deterministicalgorithm which takes as input a prime p, outputs the numberof solutions to the congruence equation f = 0 op, and runs in bit operations, for any >0. This improves upon the elementary estimate of bit operations, where n is the number of variables,which can be achieved using Berlekamp's root counting algorithm.2000 Mathematics Subject Classification 11Y99, 11M38, 11T99.     

A Fast Galerkin Algorithm for Singular Integral Equations

A recent paper (Delves, 1977) described a variant of the Galerkinmethod for linear Fredholm integral equations of the secondkind with smooth kernels, for which the total solution timeusing N expansion functions is (N² ln N) compared with the standardGalerkin count of (N³). We describe here a modification of thismethod which retains this operations count and which is applicableto weakly singular Fredholm equations of the form where K₀(x, y) is a smooth kernel and Q contains a known singularity.Particular cases treated in detail include Fredholm equationswith Green's function kernels, or with kernels having logarithmicsingularities; and linear Volterra equations with either regularkernels or of Abel type. The case when g(x) and/or f(x) containsa known singularity is also treated. The method described yieldsboth a priori and a posteriori error estimates which are cheapto compute; for smooth kernels (Q = 1) it yields a modifiedform of the algorithm described in Delves (1977) with the advantagethat the iterative scheme required to solve the equations in(N²) operations is rather simpler than that given there.     

Poincare Series of Multi-Filtered Algebras and Partitivity

It is proved that if an algebra R over a field can be endowedwith a pointed and finite-dimensional Nⁿ-filtration such thatthe associated Nⁿ-graded algebra T is semi-commutative, thenR is left and right finitely partitive. In order to do this,a multi-variable Poincaré series for every finitely generatedgraded T-module is considered and it is shown that this Poincaréseries is a rational function. The methods apply to some iteratedOre extensions such as quantum matrices and quantum Weyl algebrasas well as to the quantized enveloping algebra of sl(+1).     

Shape-preserving interpolation by G1 and G2 PH quintic splines

The interpolation of a planar sequence of points p₀, ..., p_Nby shape-preserving G¹ or G² PH quintic splines with specifiedend conditions is considered. The shape-preservation propertyis secured by adjusting ‘tension’ parameters thatarise upon relaxing parametric continuity to geometric continuity.In the G² case, the PH spline construction is based on applyingNewton–Raphson iterations to a global system of equations,commencing with a suitable initialization strategy—thisgeneralizes the construction described previously in NumericalAlgorithms 27, 35–60 (2001). As a simpler and cheaperalternative, a shape-preserving G¹ PH quintic spline schemeis also introduced. Although the order of continuity is lower,this has the advantage of allowing construction through purelylocal equations.     

On the Structure of Minimal Left Ideals in the Largest Compactification of a Locally Compact Group

This paper is centred around a single question: can a minimalleft ideal L in G^LUC, the largest semi-group compactificationof a locally compact group G, be itself algebraically a group?Our answer is no (unless G is compact). In deriving this conclusion,we obtain for nearly all groups the stronger result that nomaximal subgroup in L can be closed. A feature of our work isthat completely different techniques are required for the connectedand totally disconnected cases. For the former, we can relyon the extensive structure theory of connected, non-compact,locally compact groups to derive the solution from the commutativecase, using some reduction lemmas. The latter directly involvestopological dynamics; we construct a compact space and an actionof G on it which has pathological properties. We obtain otherresults as tools towards our main goal or as consequences ofour methods. Thus we find an extension to earlier work on therelationship between minimal left ideals in G^LUC and H^LUC whenH is a closed subgroup of G with G/H compact. We show that thedistal compactification of G is finite if and only if the almostperiodic compactification of G is finite. Finally, we use ourmethods to show that there is no finite subset of G^LUC invariantunder the right action of G when G is an almost connected groupor an IN-group.     

Cat(0) Groups with Non-Locally Connected Boundary

The main theorem shows that whenever certain amalgamated productsact geometrically on a CAT(0) space, the space has non-locallyconnected boundary. One can now easily construct a wide varietyof examples of one-ended CAT(0) groups with non-locally connectedboundary. Applications of this theorem to right-angled Coxeterand Artin groups are considered. In particular, it is shownthat the natural CAT(0) space on which a right-angled Artingroup acts has locally connected boundary if and only if thegroup is Zⁿ for some n.     

The Existence of Periodic and Subharmonic Solutions of Subquadratic Second Order Difference Equations

By critical point theory, a new approach is provided to studythe existence of periodic and subharmonic solutions of the secondorder difference equation where f C(R x R^m, R^m), f(t+M,z)+f(t,z) for any (t, z)R x R^mand M is a positive integer. This is probably the first timecritical point theory has been applied to deal with the existenceof periodic solutions of difference systems.     

Numerical Investigations into the Stokes Phenomenon. II

The Stokes phenomenon associated with the differential equationsW " = WZ (z²–a²) and W" = w(z² –a²)(x²–b²)isconsidered. As an application to the method introduced in paper I, somenumerical and analytical results concerning the Stokes constantsof these equations are presented.