Clémentin Tayou Djamegni
email: dtayou@cril.univ-artois.fr

Synthesis Of Space-Time Optimal Systolic Algorithms For The Cholesky Factorization †

Keywords: Parallel processing, projection methods, timing function, allocation function, space-time complexity, re-indexation

In this paper we study the synthesis of space-time optimal systolic arrays for the Cholesky Factorization (CF). First, we discuss previous allocation methods and their application to CF. Second, stemming from a new allocation method we derive a space-time optimal array, with nearest neighbor connections, that requires 3N + Θ(1) time steps and N 2 /8 + Θ(N) processors, where N is the size of the problem. The number of processors required by this new design improves the best previously known bound, N 2 /6 + Θ(N), induced by previous allocation methods. This is the first contribution of the paper. The second contribution stemms from the fact that the paper also introduces a new allocation method that suggests to first perform index transformations on the initial dependence graph of a given system of uniform recurrent equations before applying the weakest allocation method, the projection method.

Introduction

The Cholesky Factorization (CF) is an important problem in computer science. Algorithms such as CF are kernels of many numeric or signal processing programs. Because of the large number of arithmetic operations, Θ(N 3 ) where N is the size of the matrix, required by the CF a number of research works have been devoted to its parallelization [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF][START_REF] Gupta | Design, Implementation, and Evaluation of Banded Linear Solver For Distributed-Memory Parallel Computers[END_REF][START_REF] Liu | Computational models and task scheduling for parallel sparse cholesky factorization[END_REF]. In [START_REF] Liu | Computational models and task scheduling for parallel sparse cholesky factorization[END_REF] Liu identifies three potential levels of granularity in a parallel implementation of the CF:

1. fine-grain, in which each task consists of only on one or two floating point operations. Fine-grain parallelism is available either for dense or sparse matrices.

2. medium-grain, in which each task is a single column operation. Medium-grain parallelism is also available either for dence or sparse matrices.

3. large-grain, in which each task is the computation of an entire group of columns. Large-grain parallelism, at the level of subtrees of the elimination tree [START_REF] Liu | Computational models and task scheduling for parallel sparse cholesky factorization[END_REF], is available only in the sparse case.

Hereafter we focus on fine-grain parallelism. This parallelism can be exploited effectively by massively parallel computers such as SIMD computers and systolic arrays.

Systolic arrays as introduced by Kung and Leiserson [START_REF] Kung | Why Systolic Architecture ?[END_REF] form an attractive class of special-purpose parallel architectures suitable for an implementation in VLSI. A systolic array consists of a large number of elementary processors, also called processing element (PE), which are regularly connected in a nearest neighbor fashion. Each PE is equipped with a limited storage and operates on a small part of the problem to solve. As VLSI enables inexpensive special-purposes chips, systolic arrays are typically used as back-end, special-purpose devices to meet high performance requirements. A number of such arrays are currently used to accelerate computations arising in bioinformatics, biology and chemistry (http://www.irisa.fr/cosi/SAMBA, http://www.timelogic.com, http://www.paracel.com, http://www.cse.ucsc.edu/research/kestrel ) among others.

Most of the early systolic arrays were designed in an ad hoc case-by-case manner. But, this case-bycase approach requires an apostoriori verification to guarantee the correctness of the resulting design. In recent years there has been a great deal of effort on developping unifying theories for automatically synthesizing such arrays. It is well known that the standard methodology [START_REF] Moldovan | On the analysis and synthesis of VLSI algorithms[END_REF][START_REF] Quinton | Automatic synthesis of systolic array from uniform recurrence equations[END_REF][START_REF] Quinton | The mapping of linear equations on regular arrays[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays with control signal from recurrence equations[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays from recurrences equations[END_REF][START_REF] Sakho | Methode de conception d'algorithmes paralleles pour reseaux reguliers[END_REF] for the systematic synthesis of systolic array proceeds in four points:

1. The starting point is a solution of the problem to solve in term of a system of recurrent equations (SREs).

2. The second point deals with the uniformization of the SREs. This point leads to a system of uniform recurrent equations (SUREs) associated to a dependence graph G = (D,U) in which each node corresponds to a task and each link corresponds to a dependency between two elementary computations, also called task.

3. The third point defines a timing function (or schedule) t : D → N which gives the computation date t(v) of each task v of D, assuming that all tasks are of unit delay. A schedule is optimal if the corresponding execution time (or time steps count) is the length of the longest path of the dependence graph G.

4. The last point defines an allocation function which assigns the tasks to the processors of a systolic array so as to avoid computation conflict, i.e no two tasks with the same execution date should be executed by the same PE. An allocation function is optimal if the PEs count of the resulting array is the potential parallelism , i.e the maximum number of tasks that are scheduled to be executed at the same date.

The standard methodology poses a number of interesting optimization problems.

1. The problem of how to find a linear schedule that minimizes the execution time over all possible linear schedules associated to a given SUREs has been investigated by several authors. Approaches, based on integer programming, to a general solution are proposed in [START_REF] Shang | Time optimal linear schedules for algorithms with uniform dependencies[END_REF][START_REF] Thiele | Resource constrained scheduling of uniform algorithms[END_REF]. Note that the resulting linear schedule may not correspond to an optimal schedule.

2. The problem of transforming a SREs into a SUREs that leads to a timing function that requires the minimum possible execution time has attracted special interest. In other words, the question is to minimize the execution time independently of the uniformization of the initial SREs. This question remains open although there are now well defined methods [START_REF] Quinton | The mapping of linear equations on regular arrays[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays with control signal from recurrence equations[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays from recurrences equations[END_REF][START_REF] Yaacoby | Bounded broadcast in systolic arrays[END_REF] to systematically transform most Affine Recurrent Equations (AREs) into a SUREs. This open question is investigated in [START_REF] Djamegni | Derivation of Systolic Algorithms For the Algebraic Path Problem by Recurrence Transformations[END_REF], by Djamegni et al., for the Algebraic Path Problem (APP). In their paper the authors introduce a new uniformization technique that transforms the initial SREs (associated to the APP) into a new SUREs. The new SUREs leads to a piecewise affine schedule of 4n + Θ(1) steps, where n is the size of the APP. This is a significant improvement over the number of steps, 5n + Θ(1), of schedules induced by the earlier uniformization technique [START_REF] Benaini | Space-minimal systolic arrays for Gaussian elimination and the algebraic path problem[END_REF].

3. The problem of finding an optimal timing function for a given SUREs so as to minimize the paralelism rate has not yet received a full answer. In other words, the question is to minimize the potential parallelism independently of the timing function. Integer progamming techniques can be used to find the best affine schedule possible. However, the time spent to find such an affine schedule cannot be neglected [START_REF] Darte | Synthesizing systolic arrays: Some recent developments[END_REF]. This open question is investigated in [START_REF] Djamegni | Scheduling of the DAG Associated with Pipeline Inversion of Triangular Matrices[END_REF], by Djamegni et al., for the Triangular Matrix Inversion (TMI). These authors have proposed an optimal piecewise affine timing function with a potential parallelism of the order of n 2 /8 + Θ(n), where n is the size of the triangular matrix. This is a significant improvement over the minimal potential parallelism n 2 /6 + Θ(n) provided by optimal affine timing functions.

In this paper, we are interested in the design of a space-time optimal systolic array for the CF. The main difficulty of this problem is to meet the last (fourth) optimization criterion. In the following we briefly sommarize previous works related to this design constraint.

1. Projection Method [START_REF] Moldovan | On the analysis and synthesis of VLSI algorithms[END_REF][START_REF] Quinton | Automatic synthesis of systolic array from uniform recurrence equations[END_REF][START_REF] Quinton | The mapping of linear equations on regular arrays[END_REF]. This method corresponds to linear allocations. Such allocations are realized by projecting the dependence graph G along a direction p. All the tasks belonging to a same line of direction p are assigned to the same PE. The main drawback of this allocation technique is the low PE utilization occuring in the resulting array [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF]. Wong and Delosme [START_REF] Wong | Space-optimal linear processor allocation for systolic arrays synthesis[END_REF], Ganapathy and Wah [START_REF] Ganapathy | Optimal synthesis of algorithm-specific lower-dimensional processor arrays[END_REF] use integer programming to get the best linear allocation possible. However, such a linear allocation may not correspond to an optimal allocation. For the CF the minimal PEs count obtained by projecting the dependence graph is N 2 /2 + Θ(N). [START_REF] Bu | Processor clustering for the design of optimal fixed-size systolic arrays[END_REF][START_REF] Clauss | Calculus of space-optimal mappings of systolic algorithms on processor arrays[END_REF][START_REF] Darte | Synthesizing systolic arrays: Some recent developments[END_REF]. The starting point is a systolic array obtained from the projection method in which all PE works one step over x, with x ≥ 2. Then, groups of x neighboring PEs having disjoint working time steps are grouped into a single one. As a consequence, the PEs count of the initial array is reduced by a factor of x. This allocation technique do not guarantee space-optimality. For the CF this method permits to reduce the PEs count from [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF]. As in the grouping method, the starting point is an array obtained from the projection method. Then, the initial array is partionned into a number of PEs segments parallel to a direction called partition direction. The tasks of each segment are reallocated so as to minimize the PEs count on each segment. This approach do not guarantee space-optimality. For the CF this technique reduces the PEs count from N 2 /2 + Θ(N) to N 2 /6 + Θ(N) [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF]. Although this represents a significant improvement, this design is not space optimal as the potential parallelism of the CF is N 2 /8 + Θ(N) [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF].

Grouping (or Clustering) Method

N 2 /2 + Θ(N) to N 2 /4 + Θ(N).

Instruction Shifts Method

4.

Piling Method [START_REF] Benaini | Space-minimal systolic arrays for Gaussian elimination and the algebraic path problem[END_REF][START_REF] Clauss | Calculus of space-optimal mappings of systolic algorithms on processor arrays[END_REF]. First, from a given dependence graph and affine schedule, a set M of tasks is found such that all tasks in the set are scheduled to be executed at the same time and the set size | M | is maximal. Second, an allocation method is applied to assign the tasks of the dependence graph to PEs. Any PE which has not been assigned to execute a task of M is piled to a PE which executes a task of M and has disjoint working time steps. However, piling PEs results in long range communications such as spiral links and increases irregularity for the resulting arrays. In this paper, we seek to avoid this.

5.

Partition Method [START_REF] Sakho | Methode de conception d'algorithmes paralleles pour reseaux reguliers[END_REF][START_REF] Tchuenté | Parallel Computation on regular arrays[END_REF]. The starting point is to partition the dependence graph G into a number of sub-graphs of lower dimension. Then the tasks of each sub-graph are allocated to PEs so as to minimize the PEs count on each sub-graph. This allocation heuristic leads to an array of n 2 /8+θ(n) PEs for the Dynamic Programming (DP), where n is the size of the problem [START_REF] Louka | Dynamic programming on two-dimensional systolic arrays[END_REF]. In [START_REF] Djamegni | A New Dynamic Programming Algorithm on two dimensional arrays[END_REF] Djamegni et al. reduces the PEs count of the DP to n 2 /10 + θ(n). This better solution is obtained by merging nodes of the dependence graph associated with de DP before applying the partition method. All these solutions are not space-optimal as they are based on the earliest optimal timing function whose the potential parallelism is n 2 /14 + Θ(n). The partition method is also used in [START_REF] Djamegni | Derivation of Systolic Algorithms For the Algebraic Path Problem by Recurrence Transformations[END_REF] by Djamegni et al. to derive a space-optimal array for the APP and in [START_REF] Bermond | Parallelisation of the Gaussian elimination on systolic arrays[END_REF][START_REF] Bermond | Parallelisation of the Gauss elimination on systolic arrays[END_REF] by Bermond et al. to derive various arrays for the Gaussian Elimination (GE). However these GE solutions are not space-optimal. A Space-time optimal array for the GE is proposed in [START_REF] Benaini | Space-minimal systolic arrays for Gaussian elimination and the algebraic path problem[END_REF] by Benaini and Robert. For CF the partition method leads to an array of N 2 /6 + Θ(N) PEs.

The weakest allocation technique, in term of the resulting PEs count, seems to be the projection method. The most interesting seem to be the instruction shifts method and the partition method. Combination of different allocation techniques is possible. For instance, in [START_REF] Djamegni | Scheduling of the DAG Associated with Pipeline Inversion of Triangular Matrices[END_REF] Djamegni et al. show how one can combine projection, piling and partition methods to design a space-optimal array for the TMI when the schedule corresponds to a piecewise affine timing function. However, their design do not correspond to a systolic array because of long-range communications occuring in the array.

We believe that it is important to investigate the problem of designing space-optimal arrays based on domain transformations, given that: (i) there are tools that propose to (semi) automatically generate application specific VLSI processor arrays, (ii) such arrays are becoming more and more powerful (iii) systolic array synthesis methods find applications in parallelizing compilers. For this last point, the PAF (Paralléliseur Automatique de Fortran) project [START_REF] Fautrier | Dataflow analysis of array and scalar references[END_REF] uses a generalization of systolic schedule and allocation techniques for generating parallel code. The LooPo project [START_REF] Griebl | The loop parallilizer LooPo[END_REF] at the University of Passau explores parallelization with systolic synthesis methods, as does the OPERA project [START_REF] Mongenet | Data compiling for systems of uniform recurrence equations[END_REF] at the University of Strasbourg. Systolic schedule and allocation techniques are also used in [START_REF] Gupta | Design, Implementation, and Evaluation of Banded Linear Solver For Distributed-Memory Parallel Computers[END_REF] to compute CF on distributed memory parallel computers. In this paper, we derive a space-time optimal systolic array for the CF that requires 3N + Θ(1) time steps and N 2 /8 + Θ(N) PEs. This constitutes the first contribution of the paper. The second contribution stemms from the fact that this new array is obtained from a new allocation strategy that suggests to re-index the initial dependence graph of the CF before applying the weakest allocation method, the projection method. As this new allocation strategy is based on re-indexing transformations, it could be integrated in parallelizing compilers and tools.

Throughout this paper we will use notation [z → z′] which expresses a causal dependency between the index points z and z′, i.e results of calculations associated to point z are needed by calculations assigned to point z′. We will also use the following definition: a plane is said to be parallel to direction < a, b > if it is parallel to vectors a and b.

The rest of the paper is organized as follows. Section 2 discusses the application of previous allocations methods to CF. Section 3 presents our contribution. This section applies a new allocation strategy to the CF, and this results in a space-time optimal array that improves previous solutions. Concluding remarks are stated in the last section.

Deriving Systolic Arrays From Previous Allocation Techniques

The CF is defined as follows: Given a N × N symetric positive definite matrix A, the CF calculates a lower triangular matrix L such that A = LL t . It is defined by the following well known affine recurrence equations: For (i, j, k)

∈ D = {1 ≤ j ≤ i ≤ N ∧ 0 ≤ k ≤ j} L(i, j, k) =            A j,i if 1 ≤ j ≤ i ≤ N ∧ k = 0 L(i, j, k -1)/L( j, j, j -1) if 1 ≤ i ≤ N ∧ 1 ≤ j ≤ i -1 ∧ k = j L(i, j, k -1) 1/2 if 1 ≤ i ≤ N ∧ j = i ∧ k = i L(i, j, k -1) -L(i, k, k) if 1 ≤ j ≤ i ≤ N ∧ 1 ≤ k ≤ j -1 × L( j, k, k) (1)
Following the standard methodology for the systematic synthesis of systolic architectures [START_REF] Moldovan | On the analysis and synthesis of VLSI algorithms[END_REF][START_REF] Quinton | Automatic synthesis of systolic array from uniform recurrence equations[END_REF][START_REF] Quinton | The mapping of linear equations on regular arrays[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays with control signal from recurrence equations[END_REF][START_REF] Rajopadhye | Synthesizing systolic arrays from recurrences equations[END_REF][START_REF] Sakho | Methode de conception d'algorithmes paralleles pour reseaux reguliers[END_REF] we first derive a uniform version of [START_REF] Benaini | Space-minimal systolic arrays for Gaussian elimination and the algebraic path problem[END_REF]. Regarding the dependencies of (1) a uniform version S can be obtained with (1, 0, 0), (0, 1, 0) and (0, 0, 1) as the dependence vectors [START_REF] Quinton | The mapping of linear equations on regular arrays[END_REF], and this without changing the domain D of equations ( 1). An optimal timing function corresponding to such a uniformization is t(i, j, k) = i + j + k. The dependence graph G and the timing function are illustrated in figure 1. In this figure, we have not draw all the dependence vectors of direction (0, 0, 1) for sake of clarity.

By projecting the domain D of equations S along vector p1 = (1, 1, 0), we obtain a triangular orthoganally connected array of N(N + 1)/2 processors which solves the CF in optimal time 3N + Θ(1). In the resulting array, all PE is active only once over two time steps. Using the grouping method, the array can be compressed by a factor of 2, thereby reducing the PEs count to N 2 /4 + Θ(N). Note that if we project D along vector p2 = (1, 0, 0) we also obtain a triangular orthoganally connected array of N(N + 1)/2 processors. But this last array can not be compressed by the grouping method as all PE is active at any time step between its first and last calculations. On the other hand, the space complexity of this array has been reduced to N 2 /6 + Θ(N) [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF] by applying the instruction shifts method with the partition direction a = (0, 1, 1). This is a significant improvement over the space complexity of the initial array. However this array is not space-optimal as the potential parallelism of the problem is N 2 /8 + Θ(N) [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF]. Now let apply the partition method [START_REF] Sakho | Methode de conception d'algorithmes paralleles pour reseaux reguliers[END_REF][START_REF] Tchuenté | Parallel Computation on regular arrays[END_REF]. To this end, we first consider the intersections of the dependence graph G with a number of planes of direction < (1, 1, 0), (0, 0, 1) >. This partitions

G into N sub-graphs, G h = {(x, y, z) ∈ G | x -y = h -1}, h = 1, 2, ... N.
Then the tasks of each sub-graph are seperately allocated so as to minimize the PEs count for each sub-graph as in [START_REF] Louka | Triangular matrix inversion on systolic arrays[END_REF], where it is proposed a space-time optimal systolic array of n 2 /6 + Θ(n) PEs for TMI (n is the size of the triangular matrix). Figure 2 illustrated how the tasks of a sub-graph are allocated to PEs. The idea behind this allocation is to recursively assign at each step two columns of direction (1, 1, 0) and one line of direction (0, 0, 1) to a new PE. Sub-graph G h induces ⌈(Nh + 1)/3⌉ PEs. Thus the overall PEs count is N 2 /6 + Θ(N). Note that if the partition method is applied by partitioning G following direction < a, b > where a and b belong to {(1, 0, 0), (0, 1, 0), (0, 0, 1)} ( a = b), the resulting array will required N 2 /4 + Θ(N) PEs [START_REF] Sakho | Methode de conception d'algorithmes paralleles pour reseaux reguliers[END_REF][START_REF] Tchuenté | Parallel Computation on regular arrays[END_REF].

Our Contribution: A Space-Time Optimal Design

In this section we derive a new systolic array of N 2 /8 + Θ(N) PEs which solves the CF problem in 3N + Θ(1) steps. This is space-time optimal as the potential parallelism is N 2 /8 + Θ(N) [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF]. This better solution is obtained by performing a pre-processing by re-indexation which transforms the domain D of equations S into a new one which is more suitable for the application of projection methods.

Note that we can assume without loss of generality that the input (resp. output) points of equations S are of the form (i, j, 0) (resp. (i, j, j)), with 1 ≤ j ≤ i ≤ N. In the following we present a space-time optimal systolic array with nearest neighbor connections for the CF problem. Note that we make a distinction between nearest-neighbor arrays and local arrays where the interconnections may "jump" over one or more processors (the so-called bounded broadcast facility [START_REF] Risset | Synthesis of processors arrays for the algebraic path problem: unifying old results and deriving new architectures[END_REF][START_REF] Yaacoby | Bounded broadcast in systolic arrays[END_REF]). This often allows a constant factor of improvement, and the method can be applied to the array that we present. The derivation of this new design can be divided into three phases.

Phase 1

We first apply to system S an unimodular transformation q that transforms the initial affine timing function t(i, j, k) = i + j + k into a new one t′(i, j, k) = i. To do so we set q(i, j, k) = (i + j + k, j, k). The re-indexing q leaves inchanged the initial dependence vector (1, 0, 0) while (0, 1, 0) and (0, 0, 1) become (1, 1, 0) and (0, 1, 1) respectively. It also maintains input points (resp. output points) on their initial plane, i.e plane of cartesian equation k = 0 (resp.

-j + k = 0). Denote D (0) = {(i, j, k) ∈ Z 3 | -i + 2 j + k ≤ 0, i -j -k -N ≤ 0, -k ≤ 0, -j + k ≤ 0}.
The domain of the new system q(S) is a subset of D (0) . In the following phase we consider D (0) to simplify the presentation.

Phase 2

We now apply to D (0) a re-indexation that locates the points of {(i, j, k) ∈ D (0) | ijk -N = 0} on the plane of cartesian equation k = 0. To do so, we use the re-indexing function q 0 defined by:

q 0 (i, j, k) = (i, j, -i + j + k + N) if (i, j, k) ∈ D (0) 1 (i, j, k) if (i, j, k) ∈ D (0) 2
where D (0)

1 = {(i, j, k) ∈ D (0) | -i + j + N < 0}
2 = {(i, j, k) ∈ Z 3 | j + 2k -N ≤ 0, -k ≤ 0, -i + 2 j + 3k ≤ 0, -j ≤ 0, -i + k + N ≥ 0}. Clearly, Q (1) 1 = E ∪ F where E = {(i, j, k) ∈ Z 3 | i + 2 j + 3k -3N ≤ 0, -j ≤ 0, -k ≤ 0, 2 j + 2k -N ≤ 0, -i + k + N < 0} and F = {(i, j, k) ∈ Q (1)
1,0 | i + 2 j + 3k -3N = 1 or 2 j + 2k -N = 1}. Simple linear algebraic shows that (i, j, k) ∈ E implies i+2 j +3k -3N ≤ 0∧ j +2k -N ≤ 0 and that (i, j, k) ∈ Q (1) 2 implies i+2 j +3k -3N ≤ 0∧ j +2k -N ≤ 0. Thus D (2)

= F ∪ {(i, j, k) ∈ Z 3 | -k ≤ 0, -j ≤ 0, i + 2 j + 3k -3N ≤ 0, 2 j + 2k -N ≤ 0, -i + 2 j + 3k ≤ 0 and j + 2k -N ≤ 0}.
Let's now determine the new dependencies induced by the re-indexing q 1 . For this purpose, we first partition D (1) into three regions R 1 , R 2 and R 3 . From D (1)

= Q (0) 1 ∪ Q (0) 2 and D (1) = D (1) 1 ∪ D (1) 2 we get D (1) = (Q (0) 1 ∪ Q (0) 2 ) ∩ (D (1) 1 ∪ D (1) 2 ) = (Q (0) 1 ∩ D (1) 1 ) ∪ (Q (0) 2 ∩ D (1) 1 ) ∪ (Q (0) 2 ∩ D (1) 2 ) as Q (0) 1 ∩ D (1) 2 is empty. We set R 1 = Q (0) 1 ∩ D (1) 1 , R 2 = Q (0) 2 ∩ D (1)
1 and R 3 = Q (0) 2 ∩ D (1) 2 . Note that in region R i , the dependencies are: [z -(1, 1, 0) -→ z], [z -(1, 0, 0) -→ z], [z -(1, 0, -1) -→ z] if i = 1 and [z -(1, 0, 1) -→ z] if i = 2 or i = 3, with z ∈ R i .
We now explain how these dependencies are transformed per region by the reindexing q 1 .

Case of

Region R 1 . The dependency [z -(1, 1, 0) -→ z] become [q 1 (z) -(1, 0, 0) -→ q 1 (z)] if z ∈ D (1) 1,0 and [q 1 (z)-(1, 1, 0) -→ q 1 (z)] if z ∈ D (1) 1,1 . The dependency [z -(1, 0, 0) -→ z] become [q 1 (z)-(1, -1, 0) -→ q 1 (z)] if z ∈ D (1) 1,0 and [q 1 (z)-(1, 0, 0) -→ q 1 (z)] if z ∈ D (1) 1,1 . The dependency [z -(1, 0, -1) -→ z] become [q 1 (z) -(1, 0, -1) -→ q 1 (z)] if z ∈ R 1 . Case of Region R 2 . The dependencies [z -(1, 1, 0) -→ z] and [z -(1, 0, 0) -→ z] are transformed as in region R 1 , while the dependency [z -(1, 0, 1) -→ z] is transformed into [q 1 (z) -(1, -1, 1) -→ q 1 (z)]. Case of Region R 3 . The dependencies [z -(1, 1, 0) -→ z], [z -(1, 0, 0) -→ z] and [z -(1, 0, 1) -→ z] become [q 1 (z) -(1, 1, 0) -→ q 1 (z)], [q 1 (z) -(1, 0, 0) -→ q 1 (z)] and [q 1 (z) -(1, -1, 1) -→ q 1 (z)] respec- tively.
The resulting dependence vectors on image q 1 (R i ) of region R i by the re-indexing q 1 are:

(1, 1, 0), (1, 0, 0), (1, -1, 0) if i = 1 or i = 2, (1, -1, 1) if i = 2 or i = 3, and (1, 0, -1) if i = 1.
We are now ready to derive a space-time optimal solution using projection method. For this purpose we project domain D (2) along direction p = (1, 0, 0). The resulting array is illustrated in figure 3. It corresponds to a triangular hexagonally connected array of N 2 /8 + Θ(N) processors which is two times smaller than the size complexity of the array obtained in phase 2. Moreover this new design is spaceoptimal as the potential parallelism of the problem is [START_REF] Clauss | Optimal mapping of systolic algorithms by regular instruction shifts[END_REF] pp = N 2 /8 + Θ(N). On the other hand, the re-indexing q 1 maintains the input points on the plane of cartesian equation k = 0 and moves the output points from planesj + k = 0 and i -2 j + k -N = 0 to plane j = 0. This implies that input and output points are allocated to processors located at the border of the array. A property which permit to avoid eventual additional steps for data loading and result unloading. Thus this array solves CF problem in optimal time 3N + Θ(1). Therefore this new design is space-time optimal.

Conclusion

In this paper we have studied various allocation methods and their application to CF. In particular, we have designed a systolic array with regular nearest-neighbor connections for the CF problem that is both time-optimal and space-optimal, thereby establishing the "systolic complexity" of the CF problem. We believe that the design of a space-time optimal array represents an interesting and important contribution to the knowledge of the systolic model. This space-time optimal solution is obtained from a new allocation strategy that suggests to first perform index transformations on a dependence graph before applying the weakest allocation method, the projection method. However, the main difficulty of this allocation stragegy stemms from the definition of suitable index transformations. On the other hand, we believe that tools that permit to (semi)automatically generate application specific VLSI processors arrays, research on the parallelization of algorithms for distributed-memory massively parallel computers [START_REF] Gupta | Design, Implementation, and Evaluation of Banded Linear Solver For Distributed-Memory Parallel Computers[END_REF] and research on parallelizing compilers [START_REF] Fautrier | Dataflow analysis of array and scalar references[END_REF][START_REF] Griebl | The loop parallilizer LooPo[END_REF][START_REF] Mongenet | Data compiling for systems of uniform recurrence equations[END_REF] could benefit from systolic allocation strategies based on such index transformations.

4 .

 4 The probem of defining an allocation function that minimizes the PEs count for a given schedule remains open. Research on this optimization criterion have been presented in[1, 2,

Fig. 1 :

 1 Fig. 1: The dependence graph of the CF for N = 6

Fig. 2 :

 2 Fig. 2: Illustration of the partition method on G 1 for N = 10

Fig. 3 :

 3 Fig. 3: Array obtained for n = 12

† This work has been supported in part by the Université d'Artois, the Nord/Pas-de-Calais Région under the TACT-TIC project, the European Community FEDER Program, the French Agency Aire Développement through the project Calcul Parallèle and by the Microprocessors and Informatics Program of the United Nations University. 1365-8050 c 2002 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Acknowledgements

The author would like to thank DMTCS for multiple useful remarks and suggestions.

2 ) and D (1) = q 0 (D (0) ) = Q (0) 1 ∪Q (0) 2 . We have Q (0)

The re-indexing q 0 acts differently on the dependencies of the two regions D (0)

2 . The resulting dependence vectors are:

and (1, 0, 1), (1, 1, 0) and (1, 0, 0) in region Q (0) 2 .

Note that the re-indexing q 0 leaves inchanged the timing function t′(i, j, k) = i. Thus vector p = (1, 0, 0) is a valid projection direction. It leads to a triangular orthogonally connected array of N 2 /4 + Θ(N) processors which is two times smaller than the size complexity of the array obtained by projecting the initial domain D along the same direction. On the other hand, the re-indexing q 0 maintains the input points (resp. output points belonging to D (0)

2 ) on the plane of cartesian equation k = 0 (resp.j + k = 0) and locates the output points belonging to D (0)

Phase 3 This array can be further optimized. For this purpose we re-index the points of D (1) so as to locate the points of {(i, j, k) ∈ D (1)

on the plane of cartesian equation j = 0. To do so, we consider the re-indexing function q 1 defined by:

where

1,1 , D (2) = q 1 (D (1) ), Q (1)

1 ), Q (1) 1,0 = q 1 (D (1)

1,1 = q 1 (D

1,1 ), Q (1)

2 ), α 0 = 0 and α 1 = 1 2 . We have Q (1) 1,h = {(i, j, k) ∈ Z 3 | i + 2 j + 3k -3N -2α h ≤ 0,j ≤ 0,k ≤


Gregory M Constantine

Multicolored parallelisms of isomorphic spanning trees †

Keywords: Multicolored tree, orthogonal Latin squares, multicolored matching

It is proved that a complete graph on n (> 4) vertices can be properly edge-colored with n -1 colors in such a way that the edges can be partitioned into edge disjoint multicolored isomorphic spanning trees whenever n is a power of two or five times a power of two. A spanning tree is multicolored if all n -1 colors occur among its edges.

Multicolored parallelisms in complete graphs

Throughout this paper K s denotes the complete graph on s vertices. We color the edges of K 2n with 2n -1 colors by assigning one color to each edge. Basic terminology and notation on graph theory is found in [START_REF] Berge | Principles of Combinatorics[END_REF]. The coloration is proper if whenever two edges that have one vertex in common carry different colors. A spanning tree is called multicolored if no two of its edges have the same color. Two trees are edge disjoint if they do not share common edges. Two graphs with colored edges are isomorphic if there exists a bijection σ between the sets of vertices and a bijection η between the sets of colors such that (i, j) is an edge of color c if and only if (σ(i), σ( j)) is an edge of color η(c). We investigate the possibility of producing a proper edge-coloration of K 2n such that its edges can be partitioned into edge disjoint isomorphic multicolored spanning trees. [By isomorphic multicolored spanning trees we understand a set of spanning trees, each of which is multicolored, any two spanning trees of the set being isomorphic as uncolored spanning trees.] When this is possible to accomplish we obtain what we call a multicolored tree parallelism for K 2n .

When no coloring is involved, it is well-known, and a classical result of Euler, that the edges of K 2n can be partitioned into isomorphic spanning trees (paths, for example). Each of these spanning trees can easily be made multicolored, but the resulting edge coloration of K 2n usually fails to be proper. Indeed, there exists a proper coloration of K 8 that does not admit a multicolored path; see [START_REF] Buliga | Colored spanning trees[END_REF], [START_REF] Buliga | Colored spanning trees[END_REF]. By an inductive construction we demonstrate that a partition of the edges of K m into edge-disjoint isomorphic multicolored spanning trees that induce a proper coloration of K m is possible whenever m (> 4) is a power of two, or five times a power of two. Such a partition of the edges of K m can be viewed as a parallelism as defined in [START_REF] Cameron | Parallelisms of complete designs[END_REF], [START_REF] Cameron | Parallelisms of complete designs[END_REF], with an additional property due to color. Specifically, finding a partition as described above corresponds to an arrangement of the edges of K 2n into an array of 2n -1 rows and n columns such that each row contains all edges of some color (these edges form a perfect matching due to the fact that the graph is properly colored) and the edges in each column form a (necessarily multicolored) spanning tree the isomorphism type of which does not change from column to column. We ask, therefore, for a double parallelism of K 2n , one present in the rows of the array (perfect matchings) and the other in the columns that consist of edge disjoint isomorphic spanning trees.

The generating function of the multicolored spanning trees in any edge colored graph can be expressed as a sum of formal determinants; cf. [START_REF] Bapat | Mixed discriminants and spanning trees[END_REF] and [START_REF] Bapat | An enumerating function for spanning forests with color restrictions[END_REF]. These results have been used in constructing multicolored tree parallelisms for complete graphs on a small number of vertices. Algorithms for finding multicolored spanning trees are discussed in [START_REF] Broersma | Spanning trees with many of few colors in edge-colored graphs[END_REF]. We applied the algorithm written by [START_REF] Buliga | Colored spanning trees[END_REF] to obtain tree parallelisms for complete graphs on a small number of vertices. An application of parallelisms of complete designs to population genetics data is found in [START_REF] Banks | Nonparametric inference on mtDNA mismatches[END_REF]. Parallelisms are also useful in partitioning consecutive positive integers into sets of equal size with equal power sums; cf. [START_REF] Jacroux | On the construction of sets of integers with equal power sums[END_REF]. Discussions of colored matchings and design parallelisms to parallel computing appear in [START_REF] Harary | Parallel concepts in graph theory[END_REF].

A multicolored tree parallelism for powers of two

Our main result is the following Theorem 1 If m = 1, 3 and a multicolored tree parallelism for K 2m exists, then a multicolored tree parallelism for K 2 r m exists, for all r ≥ 1.

Proof: Starting with a multicolored tree parallelism for K 2m it suffices to prove that we can obtain a multicolored tree parallelism for K 4m . To complete the proof we simply iterate the process. Take a copy of the multicolored tree parallelism for K 2m and call it L. Take another copy of the multicolored tree parallelism for K 2m , on a disjoint set of vertices from those of L but using the same set of colors, and call it R. The graph having L ∪ R as vertices, with edges connecting any vertex of L with any vertex of R, is called B. It is apparent that we have thus constructed a graph K 4m on the vertex set L ∪ R. Edges of B are still to be colored. Color the edges of B in accordance with a pair of orthogonal Latin squares. For a definition and basic properties of orthogonal Latin squares the reader is refered to [START_REF] Constantine | Combinatorial theory and statistical design[END_REF] (p. 366). It is well known, cf. [START_REF] Bose | Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture[END_REF], that a pair of orthogonal Latin squares on n symbols exists for all n = 2, 6. Further specificity on the type of such Latin squares appears in [START_REF] Brown | A pair of orthogonal Latin squares of order 10 with four shared parallel transversals[END_REF]. The rows of the Latin squares are indexed by the vertices of L, the columns by the vertices of R. Colors used are disjoint from those used on the edges of L and R. Entries in the first Latin square represent the assignment of colors to the edges. We have thus completed an edge coloration of K 4m . It is a proper coloration, since it is proper within L and R by assumption, and the distribution of colors in accordance with the entries of the first Latin square ensures that edges emanating from each vertex carry all possible colors. We now describe the spanning tree decomposition that produces a multicolored tree parallelism for K 4m . In general denote by s(M) the set of multicolored spanning trees present in the multicolored tree parallelism of complete graph M. Let B(i) be the set of edges of B associated to positions in which symbol i occurs in the second of the orthogonal Latin squares; 1 ≤ i ≤ 2m. Consider any bijection α between the set of symbols in the second Latin square and the set s(L) ∪ s(R). The set s(L ∪ R) is now described as follows:

s(L ∪ R) = {B(i) ∪ T α(i) : 1 ≤ i ≤ 2m}.
Elements of s(L ∪ R) are spanning trees of L ∪ R. Any one of them consists of a spanning tree of L (or R) appended with a set of pendant edges B(i) for some i. They are therefore isomorphic as uncolored trees. By construction it is evident that they are multicolored. It follows that they are isomorphic multicolored spanning trees. Moreover, they are edge disjoint. The only possible overlap may occur among the edges in B. But the orthogonality of the Latin squares ensures that an edge occurs in precisely one such spanning tree. This completes the proof. ✷

Start out with the tree partition of K 8 written below. Rows represent colors, columns spanning trees. It may easily be verified that we have a proper coloration of K 8 , the four columns representing edge disjoint isomorphic multicolored spanning trees. Corollary 2 For n ≥ 1 the graph K 5•2 n admits a multicolored tree parallelism.

Edge disjoint multicolored isomorphic spanning trees

Whereas the previous section offers a multicolored tree parallelism for powers of two, and five times powers of two, this section examines settings where we fall short of a multicolored tree parallelism but are able to construct, within the context of a proper edge coloration, a large number of edge disjoint isomorphic multicolored spanning trees. It is easy to see that for an odd number of vertices any proper edge coloration of K 2m+1 using 2m + 1 colors can yield at most m edge disjoint multicolored spanning trees. Unlike in the case of an even number of vertices these spanning trees never partition the edge set of K 2m+1 . At least m edges remain uncovered. By an s-coloration of K n we understand a proper edge coloration on K n with s colors, if one exists. By a method similar to that used in the previous section we demonstrate the following Theorem 2 If a (2m + 1)-coloration of K 2m+1 that admits m edge disjoint isomorphic multicolored spanning trees on the same set of 2m colors exists, then there also exists a (2m + 1)2 rcoloration of K (2m+1)2 r that admits 2 r m edge disjoint isomorphic multicolored spanning trees, for all (m, r) = (1, 2). Furthermore, all the 2 r m spanning trees of K (2m+1)2 r in question involve the same set of (2m + 1)2 r -1 colors.

Proof: Let A be a copy of the given K 2m+1 and B another copy on a disjoint set of vertices with an obvious color preserving bijection γ between the vertices of A and B. Consider the graph A. Edges carrying the same color c form a matching of m edges and an isolated vertex; we call the isolated vertex a cvertex.

It is clear that if v is a c-vertex of A then γ(v) is a c-vertex of B.
The m spanning trees of A have edges colored with the same set of 2m colors. We denote by e the extra color that occurs in none of the spanning trees. Connect every vertex of A to every vertex of B and denote the set of resulting edges by C. We color the edges in C in accordance to a pair of orthogonal Latin squares, which exist since (m, r) = (1, 2), as follows. Label the rows of the Latin squares by vertices of A and columns by the corresponding vertices in B. We can select without loss the first Latin square to have all symbols different on the main diagonal. Symbols in the first Latin square are the colors assigned to the edges of C. The colors in the first Latin square are all different from the colors used on the edges of A (or B). The graph A ∪ B ∪ C, isomorphic to K 2(2m+1) , has all its edges colored with the 2m + 1 colors in A plus the 2m + 1 new colors in C. This coloration is not proper, however. The following change will render a proper edge coloration: recolor the diagonal entry in the first Latin square that corresponds to the vertex pair (v i , γ(v i )), with v i a c-vertex, with color c. Do this for all diagonal entries in the first Latin square. A spanning tree of the type we want is obtained by pairing up one of the given spanning trees of A (or B) with nondiagonal edges in the first Latin square that carry the same symbol in the second Latin square. By construction it follows that these spanning trees are isomorphic, multicolored, edge disjoint and 2m in number. None of these trees have edges colored with the extra color e. We now iterate the construction to obtain the stated result. This ends the proof. ✷

The premise of Theorem 2 can be verified for small values of m. In particular, it is not hard to check that this is the case for m = 2 and 3. As a consequence we obtain Corollary 3 For a (2p + 1)2 rcoloration of K (2p+1)2 r there exist p2 r edge disjoint isomorphic multicolored spanning trees each on the same set of (2p + 1)2 r -1 colors.

Though a large number of spanning trees can be obtained by the construction of Theorem 2, in general this construction is suboptimal. We can see this even in the case of K 6 . Our construction yields two edge disjoint isomorphic multicolored spanning trees. It is not hard to see that three such trees can actually be constructed.

A small case that poses some difficulty is K 12 . We were able to produce a proper coloration of K 12 that allows a partition of its edges into multicolored edge disjoint spanning trees but not all trees are isomorphic. It is listed below. The construction given in this paper does not apply to K 12 since it relies on orthogonal Latin squares of order 6; but Euler proved that they do not exist. Nevertheless, we state as follows:

Conjecture 1 Any proper coloration of the edges of a complete graph on an even number of (more than four) vertices allows a partition of the edges into multicolored isomorphic spanning trees.

  Using this multicolored tree parallelism for K 8 as the K 2m in Theorem 1 we obtain Corollary 1 For n > 2 the graph K 2 n admits a multicolored tree parallelism.

	18 34 56 27
	17 36 28 45
	16 38 47 25
	26 15 48 37
	23 14 58 67
	46 78 35 12
	57 24 13 68
	A proper coloration of K 10 , with rows representing colors and columns representing isomorphic span-
	ning trees, appears below:
	12 34 90 56 78
	24 13 69 57 80
	60 58 14 79 23
	37 89 15 40 26
	49 25 70 38 16
	50 46 28 17 39
	67 30 18 29 45
	68 19 47 20 35
	59 27 36 48 10
	Theorem 1 allows us now to conclude as follows.

† Funded by a Scaife Family Foundation grant 1365-8050 c 2002 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France


W M B Dukes

On a Unimodality Conjecture in Matroid Theory

Keywords: Matroid Theory, Unimodal Conjecture, Rank-2 matroids, Rank-3 matroids 1365-8050

A certain unimodal conjecture in matroid theory states the number of rank-r matroids on a set of size n is unimodal in r and attains its maximum at r = ⌊n/2⌋. We show that this conjecture holds up to r = 3 by constructing a map from a class of rank-2 matroids into the class of loopless rank-3 matroids. Similar inequalities are proven for the number of non-isomorphic loopless matroids, loopless matroids and matroids.

Introduction

Let us first recall some elementary definitions (further details may be found in Oxley [START_REF] Oxley | Matroid Theory[END_REF], Welsh (2) and the excellent appendix of White (3)). Let S n be a finite set of size n. A matroid M on the ground set S n is a collection of subsets I (M) of S n satisfying

• I (M) = / 0,
• if X ∈ I (M) and Y ⊆ X then Y ∈ I (M),

• if X,Y ∈ I (M) with |X| = |Y | + 1, then there exists x ∈ X\Y such that Y ∪ {x} ∈ I (M).

Sets in I (M) are called independent sets. The rank of a set X ⊆ S n , denoted r(X), is the size of the largest independent set which it contains. The rank of the matroid r(M) := r(S n ). A set X is closed (or termed a flat) if r(X ∪ {x}) = r(X) + 1 for all x ∈ S n \X. We denote by F (M) the closed sets of M. The loops of M are the elements of the rank-0 flat. Also note that x ∈ S n is a loop if it is not contained in any of the independent sets of M.

A certain unimodal conjecture in matroid theory states that the sequence of the number of non-isomorphic rank-r matroids on S n , { f r (n) : 1 r n}, is unimodal in r and attains its maximum at r = ⌊n/2⌋ (see Oxley [START_REF] Oxley | Matroid Theory[END_REF] or Welsh (4) p.300). It is easily seen that

f 1 (n) f 2 (n) holds since f 1 (n) = n and f 2 (n) = p(1) + • • • + p(n) -n,
where p(n) is the number of integer partitions of n. The step between rank-2 and rank-3 is not as clear since the exact value of f 3 (n) remains unknown. We show, through construction of a map between a class of rank-2 matroids and loopless rank-3 matroids and known values of these numbers from the On-line Encyclopedia of Integer Sequences, that this unimodal conjecture holds for these rank-2 versus rank-3 matroids. Furthermore, we show the corresponding inequalities hold for the number of rank-2, 3 non-isomorphic loopless matroids, g 2 (n) g 3 (n), loopless matroids, c 2 (n) c 3 (n), and matroids, m 2 (n) < m 3 (n).

Let b i (n) be the number of partitions of the set S n . into i parts and b(n) be the n th Bell number. Let p i (n) the number of partitions of the integer n into i parts. The number of rank-2 matroids can be enumerated through considering the points and lines of the associated geometry. We have

c 2 (n) = b(n) -1, g 2 (n) = p(n) -1 and m 2 (n) = b(n + 1) -2 n (
for proofs see Dukes [START_REF] Dukes | Enumerating Low Rank Matroids and Their Asymptotic Probability of Occurrence[END_REF]). The main results of this paper are given in Theorems 2.5, 2.6, 2.11 and 2.12.

2 Mapping rank-2 to rank-3 matroids Let M r (n) be the collection of rank-r matroids on S n . Let A r (n) be the collection of rank-r matroids on S n with at least one loop and B r (n) := M r (n)\A r (n). We define the map σ :

A 2 (n) → B 3 (n) as follows: given M ∈ A 2 (n) with loops F 0 and rank-1 flats F 1 (M) = {F 0 ∪ F 1 , . . . , F 0 ∪ F m } define M ′ = σ(M) as: F 0 (M ′ ) := { / 0} F 1 (M ′ ) := {F 0 , F 1 , . . . , F m } F 2 (M ′ ) := {F 0 ∪ F i |1 i m} ∪ {F 1 ∪ • • • ∪ F m } F 3 (M ′ ) := {S n }.
It is easily checked that these collections of flats satisfy the axioms for a loopless rank-3 matroid. For M ∈ M r (n), let us write d(M) for the number of rank-1 flats of M (which we will refer to as the degree of M). Let us mention that for any loopless matroid M, the rank-1 flats of M partition the ground set. Similarly, for any matroid, the rank-1 flats partition the ground set less the set of loops. Also note that in the collection F 2 (M ′ ), there are precisely d(M) sets containing F 0 , 2 sets containing F i (for any 1 i d(M)) and one set containing F i ∪ F j (for all 0 i = j d(M)).

The following lemma shows that to each rank-2 matroid with at least one loop, there corresponds a rank-3 loopless matroid (although not necessarily unique). The following lemma classifies those matroids which map to a unique loopless matroid in B 3 (n) and those which do not.

Lemma 2.1 Let M 1 , M 2 ∈ A 2 (n) be such that F 0 (M 1 ) = {F (1) 0 }, F 0 (M 2 ) = {F (2) 0 }, F 1 (M 1 ) = {F (1) 0 ∪ F (1) 1 , . . . , F (1) 0 ∪ F (1) d(M 1 ) } and F 1 (M 2 ) = {F (2) 0 ∪ F (2) 1 , . . . , F (2) 0 ∪ F (2) d(M 2 ) }. Then σ(M 1 ) = σ(M 2 ) if and only if d(M 1 ) = d(M 2 ) = 2 and F (1) 0 , F (1) 1 , F (1) 2 = F (2) 0 , F (2) 1 , F (2) 2 . Proof: ONLY IF: Let M 1 , M 2 ∈ A 2 (n) be such that M 1 = M 2 and σ(M 1 ) = σ(M 2 ). Let M ′ 1 := σ(M 1 ) and M ′ 2 := σ(M 2 ). Then we must have F 1 (M ′ 1 ) = F 1 (M ′ 2 ) and F 2 (M ′ 1 ) = F 2 (M ′ 2 ). Now F 1 (M ′ 1 ) = F 1 (M ′ 2 ) ⇒ d(M 1 ) = d(M 2 ) and {F (1) i } d(M 1 ) i=0 = {F (2) i } d(M 2 ) i=0 . If d(M 1 ) > 2 then we must have F (1) 0 = F (2) 0 which would imply M 1 = M 2 . Hence d(M 1 ) = 2 = d(M 2 ). This gives F 2 (M ′ 1 ) = {F (1) 0 ∪ F (1) 1 , F (1) 0 ∪ F (1) 1 , F (1) 0 ∪ F (1) 1 } = F 2 (M ′ 2 ) only if {F (1) 0 , F (1) 1 , F (1) 2 } = {F (2) 0 , F (2) 1 , F (2) 2 }. IF: This is trivial as {F (1) 0 , F (1) 1 , F (1) 2 } = {F (2) 0 , F (2) 1 , F (2) 2 } gives F 1 (M ′ 1 ) = F 1 (M ′ 2 ) and F 2 (M ′ 1 ) := F (1) 0 ∪ F (1)
1 , F

(1)

0 ∪ F (1)
1 , F

(1)

0 ∪ F (1) 1 } = F (2) 0 ∪ F (2) 1 , F (2) 0 ∪ F (2) 1 , F (2) 0 ∪ F (2) 1 } =: F 2 (M ′ 2 ). ✷ Thus it is seen for each matroid M ∈ σ(A 2 (n)) such that d(M) = 2, there are precisely three different matroids M 1 , M 2 , M 3 ∈ A 2 (n) such that σ(M 1 ) = σ(M 2 ) = σ(M 3 ) = M. Lemma 2.2 For all n 3, c 3 (n) b(n + 1) -b(n) -3 n-1 .
Proof: We show that the number of unique matroids in the image of A 2 (n) under σ is given by b

(n + 1) -b(n) -3 n-1
, thereby lower-bounding c 3 (n). In the enumeration below, we divide the matroids to be counted in the image into two classes, those matroids M with d(M) = 2 and those with d(M) > 2. The former class projects different matroids to the same matroid in B 3 (n) and through the use of the previous lemma we take care of this over-counting, hence

# {σ(M)|M ∈ A 2 (n)} = # {σ(M)|M ∈ A 2 (n) and d(M) = 2} + n ∑ i=3 # {σ(M)|M ∈ A 2 (n) and d(M) = i} = 1 3 # {M|M ∈ A 2 (n) and d(M) = 2} + n ∑ i=3 # {σ(M)|M ∈ A 2 (n) and d(M) = i} = n ∑ i=2 # {σ(M)|M ∈ A 2 (n) and d(M) = i} - 2 3 # {M|M ∈ A 2 (n) and d(M) = 2} = #A 2 (n) - 2 3 # {M|M ∈ A 2 (n) and d(M) = 2} = b(n + 1) -2 n -(b(n) -1) - 2 3 # {M|M ∈ A 2 (n) and d(M) = 2} . Note that # {M|M ∈ A 2 (n) and d(M) = 2} = ∑ n-1 l=2 n l b 2 (l) and b 2 (l) = 1 2 ∑ l-1 j=1 l j = 2 l-1 -1, giving: # {M|M ∈ A 2 (n) and d(M) = 2} = n-1 ∑ l=2 n l (2 l-1 -1) = 1 2 (3 n -2 n -2n -1) -(2 n -n -2) = 3 2 (3 n-1 -2 n + 1). Thus # {σ(M)|M ∈ A 2 (n)} = b(n + 1) -2 n -b(n) + 1 - 2 3 3 2 (3 n-1 -2 n + 1) = b(n + 1) -b(n) -3 n-1 .

✷

The corresponding inequality for the number of non-isomorphic loopless matroids is proved in Lemma 2.3. We do this in a similar manner as before, by showing that each rank-2 matroid (which is not a loopless matroid) of degree greater than 3 corresponds uniquely to a rank-3 loopless matroid.

Lemma 2.3 For all n 4, g 3 (n) n-1 ∑ i=1 p(i) - 1 12 (2n 2 + 6n + 3) -1.
Proof: We show the number of non-isomorphic matroids in the image of A 2 (n) under σ is given by

∑ n-1 i=1 p(i) -1 12 (2n 2 + 6n + 3) -1 which lower bounds g 3 (n).
Let us identify A ⋆ 2 (n) ⊆ A 2 (n) by placing an ordering on the elements of S n = {x 1 , . . . ,

x n }. Given M ∈ A 2 (n) with d(M) = m, loops F 0 and rank-1 flats {F 0 ∪ F 1 , . . . , F 0 ∪ F m }, let M ∈ A ⋆ 2 (n) if and only if F 0 = {x 1 , . . . , x |F 0 | }, F 1 contains the next |F 1 | elements of S n , i.e. {x |F 0 |+1 , . . . , x |F 0 |+|F 1 | } and so forth. Define T (n) := M ∈ A ⋆ 2 (n) d(M) = 2 and |F 0 | |F 1 | |F 2 |
and for 3 i n -1, 3 j i, define

Ω i, j (n) := M ∈ A ⋆ 2 (n) d(M) = j, |F 0 | = n -i and |F 1 | • • • |F j | .

Let us now write

A ⋆⋆ 2 (n) := T (n) ∪ n-1 i=3 i j=3 Ω i, j (n) ⊆ A ⋆ 2 (n).
It is obvious that no two matroids in T (n) are isomorphic to one-another. Similarly with Ω k,l (n). We have simply reduced our class of matroids from A 2 (n) to A ⋆⋆ 2 (n) in the same manner as one moves from the set of partitions of a finite set of size n to the set of integer partitions of n.

The unions in the definition of A ⋆⋆ 2 (n) are strictly disjoint and no isomorphisms may occur between matroids in different classes or matroids in the same class. The same is true of the image of A ⋆⋆ 2 (n) under the map σ. We may directly enumerate the number of non-isomorphic matroids in B 3 (n) in the image of A ⋆⋆ 2 (n) under σ as

p 3 (n) + n-1 ∑ i=3 i ∑ j=3 p j (i).
The rightmost term is bounded below;

n-1 ∑ i=3 i ∑ j=3 p j (i) = n-1 ∑ i=2 {p(i) -p 1 (i) -p 2 (i)} = n-1 ∑ i=3 {p(i) -1 -⌊i/2⌋} = -(n -3) + n-1 ∑ i=3 p(i) - n-1 ∑ i=3 ⌊i/2⌋ =    ∑ n-1 i=1 p(i) -n(n+2) 4 + 1, n even, ∑ n-1 i=1 p(i) -(n+1) 2 4 + 1, n odd, n-1 ∑ i=1 p(i) - (n + 1) 2 4 ,
for all n 2. As for p 3 (n), from Hall (6) [p.32], we have

p 3 (n) = ⌊n 2 /12⌋, for n ≡ 3(mod 6), ⌈n 2 /12⌉, for n ≡ 3(mod 6), n 2 12 -1,
and so

g 3 (n) n-1 ∑ i=1 p(i) + n 2 12 - (n + 1) 2 4 -1 = n-1 ∑ i=1 p(i) - 1 12 (2n 2 + 6n + 3) -1.
✷

Matroids

The following lemma is needed in order to support the theorem which follows it.

Lemma 2.4 For all n 1, b(n + 1) -2 n 2 n -(1 + n). Proof: We have that b(i) 2 for all i 2. Since n 2, it follows that b(n + 1) -2 n = n ∑ i=0 n i (b(i) -1) n ∑ i=2 n i 1 = 2 n -(1 + n). ✷ Theorem 2.5 For all n > 4, c 3 (n) c 2 (n). Proof: From Lemma 2.2 we have that c 3 (n) b(n + 1) -b(n) -3 n-1 . We know c 2 (n) = b(n) -1. It suffices to show that b(n + 1) -b(n) -3 n-1 b(n) -1 for all n > 4. Let us look at the value b(n + 1) -2b(n) -3 n-1 + 2 n-1 : b(n + 1) -2b(n) -3 n-1 + 2 n-1 = n-1 ∑ i=0 n i b(i) - n-1 ∑ i=0 n -1 i b(i) - n-1 ∑ i=0 n -1 i 2 i + n-1 ∑ i=0 n -1 i = n-2 ∑ i=0 n -1 i b(i + 1) -2 i
and using Lemma 2.4,

n-2 ∑ i=1 n -1 i 2 i -(1 + i) = 3 n-1 -2 n + 1 - n-2 ∑ i=1 n -1 i i = 3 n-1 -(n + 3)2 n-2 + n.
The problem has been reduced to showing 3 n-1 -(n + 3)2 n-2 + n 2 n-1 -1 for all n 5, which is easily shown by induction. ✷

We now show the number of rank-3 matroids dominates the number of rank-2 matroids by using two things: the first is the result proved previously, that the number of rank-3 loopless matroids is at least as large as the number of rank-2 loopless matroids; the second is the first few known values of the numbers c 2 (n) and c 3 (n). The latter knowledge makes the inequality strict.

Theorem 2.6 For all n 5, m 3 (n) m 2 (n).

Proof:

The number of rank-r matroids on S n is related to the number of loopless matroids on S n by

m r (n) = n ∑ i=r n i c r (i).
In Theorem 2.5 we showed that c 3 (n) c 2 (n) for all n 5. Replacing r = 3 in the above expression and using the first few values of c 3 (n) (taken from row 3, table A058710, of Sloane ( 7)),

m 3 (n) = n ∑ i=3 n i c 3 (i) = 1 n 3 + 11 n 4 + 106 n 5 + 1232 n 6 + n ∑ i=7 n i c 3 (i) 1 n 3 + 11 n 4 + 106 n 5 + 1232 n 6 + n ∑ i=7 n i c 2 (i) = 830 n 6 + 75 n 5 -3 n 4 -3 n 3 - n 2 + n ∑ i=2 n i c 2 (i)
A simple check shows that 830 n 6 + 75 n 5 -3 n 4 -3 n 3 -n 2 is greater than zero and increasing for all n 7. From Table 1 (see Appendix), the result is also seen to hold for n = 5, 6. Equality holds only for n = 5, for all other values of n the inequality is strict. ✷

Non-isomorphic matroids

Proving the corresponding inequalities for the non-isomorphic numbers is more difficult. We first prove several lemmas related to the numbers p(n) which we will need in the proofs of the two remaining theorems.

Lemma 2.7 For all n 1, p(n + 1) p(n) + n+1 2 . Proof: The number of partitions of the integer n + 1 whose first part contains the integer 1 is precisely p(n). The number beginning with i, for any 2 i n+1 2

is at least 1 since we can have the partition n + 1 = i + (n + 1i). Also, the number n + 1 is a partition by itself, hence,

p(n + 1) p(n) + n + 1 2 -1 + 1 = p(n) + n + 1 2 . ✷ Lemma
+ • • • + n -1 2 + n 2 1 + 1 + 1 2 + • • • + n -1 2 + n 2 . (1)
Now we wish to evaluate the sum ∑ n i=2 i 2 . Let n = 2m + 1 for some m 1, then

n ∑ i=2 i 2 = 2m+1 ∑ i=2 i 2 = m ∑ i=1 2i 2 + 2i + 1 2 = n 2 n 2 .
Note that, by duality, an immediate Corollary of Theorems 2.6 and 2.12 is the following.

Corollary 2.13 For all n 6,

f n (n) f n-1 (n) f n-2 (n) f n-3 (n) m n (n) m n-1 (n) m n-2 (n) m n-3 (n).
Appendix

n

Table 1 :

 1 Known values for the number of rank-2 and rank-3 matroids taken from Sloane[START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF].

		2 3 4	5	6	7	8	OLEIS Number Row
	g 2 (n)	1 2 4	6	10	14	21	A058716	2
	g 3 (n)	1 3	9	25	70	217	A058716	3
	f 2 (n)	1 3 7	13	23	37	58	A053534	2
	f 3 (n)	1 4	13	38	108	325	A053534	3
	c 2 (n)	1 4 14 31	202	876	4139	A058710	2
	c 3 (n)	1 11 106 1232 22172 803583	A058710	3
	m 2 (n) 1 7 36 171 813	4012	20891	A058669	2
	m 3 (n)	1 15 171 2053 33442 1022217	A058669	3

Acknowledgements

The author would like to thank the anonymous referees for their helpful comments.

For the n = 2m case with m 1, we simply remove the last term in the previous expression, thus

Continuing to the inequality in Equation 1 above,

For all those partitions with x 1 2, we see that reducing x 1 by 1 will yield a partition of n. Thus an upper bound on the number beginning with x 2 2 is p(n). For all partitions starting with x 1 = 2, we see that x 2 = 1, thus we may remove all those sequences with

this means all those partitions with x 3 + . . . + x k = n -2 and 1 x 3 • • • x k of which there are p(n -2).

Thus we see that p(n + 1) < p(n) + p(n)p(n -2) = 2p(n)p(n -2). From lemma 2.8 we know that for n 3,

Now, we see that the simple inequality (3n -13)(n -1) 0 holds for all n 13 3 , i.e. (n 2 -4n+7)

4

(n+2) (2(7) 2 + 6(7) + 3) < 27. Suppose it to be true for some n = m 7, then:

. From above, this gives

and using Lemma 2.9,

(2(m + 1) 2 + 6(m + 1) + 3).

✷

Theorem 2.11 For all n 5, g 3 (n) g 2 (n).

Proof:

We have that g 2 (n) = p(n) -1. Also, we know from Theorem 2.6 that

) for all n 7. Combining these facts gives

which is g 2 (n). From Table 1, the result is also seen to hold for n = 5, 6. ✷ Theorem 2.12 For all n 5, f 3 (n) f 2 (n).

Proof:

The number of non-isomorphic rank-3 matroids on S n in terms of loopless non-isomorphic rank-3 matroids is given through the relation f 3 (n) = ∑ n i=3 g 3 (i) for all n 3. The value f 2 (n) = p(1) + p(2) + . . . + p(n)n for all n 2. From Theorem 2.11 we have g 3 (n) g 2 (n) for all n 7. Applying the above expression for f 3 (n), using the known value for g 3 (n) (from Sloane [START_REF] Sloane | The On-line Encyclopedia of Integer Sequences[END_REF], row 3 of A058716) and assuming n 7,

which is precisely f 2 (n). From Table 1, the result is seen to hold for n = 5, 6. Note that the above inequality is strict for n 6 and equality holds only for n = 5. ✷