Browse Prior Art Database

Algorithm to Generate Structures of Circulant (Cyclic) Matrices

IP.com Disclosure Number: IPCOM000076307D
Original Publication Date: 1972-Feb-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Reynolds, SW: AUTHOR

Abstract

An algorithm is described for the generation of structures or circulant (cyclic) matrices. The principal advantage of this algorithm is that it permits the generation of many N by N circulant matrices by entering only 1/N/th/ of the data required by such a structure.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 1

Algorithm to Generate Structures of Circulant (Cyclic) Matrices

An algorithm is described for the generation of structures or circulant (cyclic) matrices. The principal advantage of this algorithm is that it permits the generation of many N by N circulant matrices by entering only 1/N/th/ of the data required by such a structure.

Briefly, an N by N matrix A is said to be a circulant if A[1,J] = A[1+1, J+1] for all 1, J where the indices are taken modulo N. An example or a 4 by 4 circulant is 4 1 0 1 1 4 1 0 0 1 4 1 1 0 1 4.

The algorithm to be presented provides a method for generating many circulant matrices of the same order. It is particularly adaptable to array-oriented languages, and its implementation will be presented using APL/360.

Let A denote a vector representing the desired number of structures of N by N circulant matrices. Let B denote a numeric, or character, vector consisting of the catenation of elements of the first row for each matrix desired. The algorithm, which works in either 0 or 1 origin indexing, is described as follows: 1) The order
(N) of the matrices which are to be generated is given by the last component of the vector A. 2) The total number of elements (D) required by the structure is the product of all of the components of A except the last. The vector B is reshaped to the dimension specified by D. Thus, if there were not D components in the vector B, the APL dyadic reshape function would cause the existing elements of B to "wrap ar...