Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Build up a given matrix from a set of matrices

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 16 Jun, 2013 20:16:09

Message: 1 of 11

Given an (Nx2) matrix, A, (row size is user-set as N), and a separate set, U, of distinct matrices or row-vectors all having M=2 columns, but with varying row-sizes, find all possible non-intersecting constructions of the given matrix from the set of small smaller matrices/row vectors. The set of matrices/row vectors need not be exhausted, meaning that some of these matrices/row vectors may not be used in any construction of the given matrix, A.

The matrices are all integer-valued and their second columns are binary, but this is not relevant to problem.

For example, given A and a set U = {A1, A2, A3}, where
A = [3794 0; 2647 1; 3095 0; 3739 1; 2697 1; 3176 1; 3817 1; 1051 1; 1699 1; 1051 0; 1686 1; 1146 1; 1794 0; 647 1; 1095 0; 1739 1; 697 1; 1176 1; 1817 1; 3051 1; 3699 1; 3051 0; 3686 1; 3146 1]; % (24x2)

and

A1 = [3051 1; 3699 1]; % (2x2)
A2 = [1051 1; 1699 1]; % (2x2)
A3 = [3794 0; 2647 1; 3095 0; 3739 1; 2697 1; 3176 1; 3817 1; 1051 0; 1686 1; 1146 1; 1794 0; 647 1; 1095 0; 1739 1; 697 1; 1176 1; 1817 1; 3051 0; 3686 1; 3146 1]; % (20x2)

then A can be constructed (if I typed everything in correctly) via row-aligning A1, A2, A3, as confirmed by:

all(ismember(A, [A1; A2; A3], 'rows')) = 1 % check that the rows of A and its building blocks are the same; order does not matter

The row-intersections of A1, A2, and A3 are empty, meaning that not only can A1, A2, and A3 combine to form A, but there will be no 'pieces' left over. Notice, also, that I don't require an order in the concatenation, only that (1) all of the rows of A1, A2, A3 are used and (2) there is no row-overlap between A1, A2, A3. In short, this makes A a disjoint, independent "union" of A1, A2, and A3. Finally, the matrices in the set U all have less rows than will A.

This was a simple example where the matrix A is not huge, we only had three other matrices to work with, and these matrices were all used up. In general, the matrix is not too large (size(A,1) < 200), but the number of matrices in the set U can increase, with U possibly containing 30 matrices that could possibly be used to "build up" A.

I have coded this successfully already, and now would like to optimize. First I see if each individual matrix in the set U={A1, A2, ... A30} "builds up" to A (would be a rotation of A at this level). Then I do the same for pairs of matrices in U (repeats allowed), (so check if A1 and A1 "build up" to A, A1 and A2, ... A1 and A30, then A2 and A3 and continue), then triplets, etc. I use matlab's combnk function here. The algorithm is "done" when the first amalgamation of A is found.

My algorithm works for smaller-sized matrices, A, and smaller sets of building matrices, U, but is very slow and computationally-intense otherwise. Would anyone please have any ideas how I could optimize this, or suggest a different approach? Thanks!

Subject: Build up a given matrix from a set of matrices

From: dpb

Date: 17 Jun, 2013 13:00:08

Message: 2 of 11

On 6/16/2013 3:16 PM, Matthew wrote:
> Given an (Nx2) matrix, A, (row size is user-set as N), and a separate
> set, U, of distinct matrices or row-vectors all having M=2 columns, but
> with varying row-sizes, find all possible non-intersecting constructions
> of the given matrix from the set of small smaller matrices/row vectors.
> The set of matrices/row vectors need not be exhausted, meaning that some
> of these matrices/row vectors may not be used in any construction of the
> given matrix, A.
>
> The matrices are all integer-valued and their second columns are binary,
> but this is not relevant to problem.

Well, the size being commensurate and the integer-value certainly have
bearing on the implementation...

...

> I have coded this successfully already, and now would like to optimize.
> First I see if each individual matrix in the set U={A1, A2, ... A30}
> "builds up" to A (would be a rotation of A at this level). Then I do the
> same for pairs of matrices in U (repeats allowed), (so check if A1 and
> A1 "build up" to A, A1 and A2, ... A1 and A30, then A2 and A3 and
> continue), then triplets, etc. I use matlab's combnk function here. The
> algorithm is "done" when the first amalgamation of A is found.
>
> My algorithm works for smaller-sized matrices, A, and smaller sets of
> building matrices, U, but is very slow and computationally-intense
> otherwise. Would anyone please have any ideas how I could optimize this,
> or suggest a different approach? Thanks!

W/O taking more time than have at moment to really work on it, the first
(and only) thought that comes to mind would be to first eliminate any Ai
that aren't candidates by verifying that they don't contain invalid
entries to at least limit the size of the search field as much as
possible. If the components are such that it's known a priori that all
are valid candidates then this obviously is no help.

--

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 17 Jun, 2013 14:50:10

Message: 3 of 11

dpb <none@non.net> wrote in message <kpn18r$uiv$1@speranza.aioe.org>...
> On 6/16/2013 3:16 PM, Matthew wrote:
> > Given an (Nx2) matrix, A, (row size is user-set as N), and a separate
> > set, U, of distinct matrices or row-vectors all having M=2 columns, but
> > with varying row-sizes, find all possible non-intersecting constructions
> > of the given matrix from the set of small smaller matrices/row vectors.
> > The set of matrices/row vectors need not be exhausted, meaning that some
> > of these matrices/row vectors may not be used in any construction of the
> > given matrix, A.
> >
> > The matrices are all integer-valued and their second columns are binary,
> > but this is not relevant to problem.
>
> Well, the size being commensurate and the integer-value certainly have
> bearing on the implementation...
>
> ...
>
> > I have coded this successfully already, and now would like to optimize.
> > First I see if each individual matrix in the set U={A1, A2, ... A30}
> > "builds up" to A (would be a rotation of A at this level). Then I do the
> > same for pairs of matrices in U (repeats allowed), (so check if A1 and
> > A1 "build up" to A, A1 and A2, ... A1 and A30, then A2 and A3 and
> > continue), then triplets, etc. I use matlab's combnk function here. The
> > algorithm is "done" when the first amalgamation of A is found.
> >
> > My algorithm works for smaller-sized matrices, A, and smaller sets of
> > building matrices, U, but is very slow and computationally-intense
> > otherwise. Would anyone please have any ideas how I could optimize this,
> > or suggest a different approach? Thanks!
>
> W/O taking more time than have at moment to really work on it, the first
> (and only) thought that comes to mind would be to first eliminate any Ai
> that aren't candidates by verifying that they don't contain invalid
> entries to at least limit the size of the search field as much as
> possible. If the components are such that it's known a priori that all
> are valid candidates then this obviously is no help.
>
> --

Thanks for looking at the post. I should have mentioned this, but, yes, I have already eliminated the Ai matrices that could not possibly be candidates. Any that belong to the set U are those that have share at least one common row with A.

Subject: Build up a given matrix from a set of matrices

From: dpb

Date: 17 Jun, 2013 17:48:15

Message: 4 of 11

On 6/17/2013 9:50 AM, Matthew wrote:
> dpb <none@non.net> wrote in message <kpn18r$uiv$1@speranza.aioe.org>...
...

> Thanks for looking at the post. I should have mentioned this, but, yes,
> I have already eliminated the Ai matrices that could not possibly be
> candidates. Any that belong to the set U are those that have share at
> least one common row with A.

I thought you said you had to use the full Ai contents for each Ai
chosen????

--

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 17 Jun, 2013 18:10:13

Message: 5 of 11

dpb <none@non.net> wrote in message <kpni51$ifn$2@speranza.aioe.org>...
> On 6/17/2013 9:50 AM, Matthew wrote:
> > dpb <none@non.net> wrote in message <kpn18r$uiv$1@speranza.aioe.org>...
> ...
>
> > Thanks for looking at the post. I should have mentioned this, but, yes,
> > I have already eliminated the Ai matrices that could not possibly be
> > candidates. Any that belong to the set U are those that have share at
> > least one common row with A.
>
> I thought you said you had to use the full Ai contents for each Ai
> chosen????
>
> --

Exactly. The contents (rows) of each Ai matrix are all members (rows) of A. What I meant was that I have already eliminated from consideration other matrices (from a much larger set) that do not completely share their rows with A.

So: each Ai can be thought of a block of the A-matrix, and we need to find a U-subset of Ais that completely build up A, with no overlapping.

Sorry for the confusion.

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 19 Jun, 2013 11:32:11

Message: 6 of 11

"Matthew" wrote in message <kpnje5$irs$1@newscl01ah.mathworks.com>...
> dpb <none@non.net> wrote in message <kpni51$ifn$2@speranza.aioe.org>...
> > On 6/17/2013 9:50 AM, Matthew wrote:
> > > dpb <none@non.net> wrote in message <kpn18r$uiv$1@speranza.aioe.org>...
> > ...
> >
> > > Thanks for looking at the post. I should have mentioned this, but, yes,
> > > I have already eliminated the Ai matrices that could not possibly be
> > > candidates. Any that belong to the set U are those that have share at
> > > least one common row with A.
> >
> > I thought you said you had to use the full Ai contents for each Ai
> > chosen????
> >
> > --
>
> Exactly. The contents (rows) of each Ai matrix are all members (rows) of A. What I meant was that I have already eliminated from consideration other matrices (from a much larger set) that do not completely share their rows with A.
>
> So: each Ai can be thought of a block of the A-matrix, and we need to find a U-subset of Ais that completely build up A, with no overlapping.
>
> Sorry for the confusion.

Anyone have any ideas? Thanks!

Subject: Build up a given matrix from a set of matrices

From: james bejon

Date: 19 Jun, 2013 19:08:13

Message: 7 of 11

Well, this is nothing to do with your algorithm as such. But the first thing that occurs to me is that you could easily convert each row into a single number; suppose, for instance, your integers are both int8; you could then make that a single int16, e.g.,

n1 = [int8(10), int8(20)];

t = typecast(n1, 'int16');

n2 = typecast(t, 'int8');

isequal(n1, n2)



You could then reduce your problem to dealing with single numbers rather than rows all the time, which might make life easier and quicker.

Meanwhile, I'll have a think about the algorithm itself and let you know if anything springs to mind...

Subject: Build up a given matrix from a set of matrices

From: james bejon

Date: 19 Jun, 2013 19:38:07

Message: 8 of 11

P.S. Could you post your algorithm that works for smaller sizes, just so I can make sure I've understood the problem correctly?

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 20 Jun, 2013 02:02:10

Message: 9 of 11

"james bejon" wrote in message <kpt1av$ila$1@newscl01ah.mathworks.com>...
> P.S. Could you post your algorithm that works for smaller sizes, just so I can make sure I've understood the problem correctly?

Here is the algorithm, taken from my research project, which works for simpler cases. In theory, it should still work for more involved situations but it is impractical in its current un-optimized form. The cell-array, M, is pre-constructed (c.f., the function's help comments), so there is no way really for me to provide a concrete example. Hopefully analyzing the algorithm will help paint a clearer picture. Thanks, I really appreciate the help.

function [yesno, Aout] = IsMatrixComplete(U, Ain, M)

% IsMatrixComplete determines (1-yes or 0-no) if a given (N x 2) matrix can
% be 'built up' or constructed as a non-intersecting row-concatenation of
% the matrices represented by the elements of the vector U.
%
% USAGE: [yesno, Aout] = IsMatrixComplete(U, Ain, M)
%
% INPUTS:
%
% U - a set of indices that references (n x 2) 'building-block'
% matrices from the (large) cell array, M
% Ain - the (N x 2) matrix which is to be decomposed into building-
% block matrices; can also start out as an (N x 7) matrix
% M - a pre-constructed cell array whose second column contains the
% actual (n x 2) building-block matrices
%
% OUTPUTS:
%
% yesno - (binary) 1 - Ain can be completely built-up; 0, otherwise
% Aout - the remainder (if any) of the rows of Ain that cannot be
% built-up

%-------------------------------------------------------------------------%
yesno = 0; % assume IsMatrixComplete == 0

% loop over all possible building-block matrices specified in U
for kk = 1:length(U)
    
    % all combinations of the numbers 1:length(U) taken kk at a time
    % this gives combinations of the indices of U from which to test the
    % building-block matrices
    T = combnk(1:length(U), kk);
    
    for nn = 1:size(T,1)
        
        % set matrices
        C = cat(1, M{U(T(nn,1:end)),2}); % concatenation
        A = Ain; % store orginal matrix
        
        % if C and A do not overlap at all, pass to next for-loop iteration
        if all(~ismember(C, A, 'rows')), continue, end
        
        % if C and A are exactly the same matrices, exit from function
        if isequal(C, A), yesno = 1; C = []; A = []; return, end
        
        iA = (1:length(Ain))'; % vector of A-indices
        nrot = 0; % number of rotations of A (see circshift loop, below)
        while (~isempty(C) && ~isempty(A))
            
            % find the indices of overlaps of C(1,:) within A
            ic = strmatch(C(1,:), A, 'exact');
            if isempty(ic)
                Clength = size(C,1);
                nrot = nrot + 1; % count number of times C is rotated
                C = circshift(C, -1);
                if nrot == Clength, break, end % allow one full rotation
                continue
            end
            nrot = 0; % reset rotation counter
            ic = ic(1); % take first instance that C and A overlap
            try % (the try-catch's are safegaurds)
                A = A(iA ~= ic,:); % remove element that A shares with C
                iA = 1:length(A); % new A-index vector
            catch
                A = A(2:end,:); % reduce A
            end
            try
                C = C(2:end,:); % reduce C
            catch
                continue
            end
            
        end % end while-loop
        
        % if C completely exhausts A, exit from function
        if isempty(C) && isempty(A), yesno = 1; return, end
        
    end % end inner for-loop(nn)
end % end outer for-loop(kk)

% if the original Ain and its reduction (remainder), A, are the same, end
if isequal(A, Ain), return, end

% if C has been exhausted, but A still survives, some of the building-block
% matrices may be repeats, so run iscomplete again
if isempty(C) && ~isempty(A)
    [yesno, Aout] = IsMatrixComplete(U, A, M);
end

Aout = A; % return the leftover rows of Ain (could be empty)

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 5 Jul, 2013 13:40:11

Message: 10 of 11

Any suggestions or ideas? Anyone?

Subject: Build up a given matrix from a set of matrices

From: Matthew

Date: 25 Jul, 2013 01:57:12

Message: 11 of 11

"Matthew" wrote in message <kpl6e9$mv7$1@newscl01ah.mathworks.com>...
> Given an (Nx2) matrix, A, (row size is user-set as N), and a separate set, U, of distinct matrices or row-vectors all having M=2 columns, but with varying row-sizes, find all possible non-intersecting constructions of the given matrix from the set of small smaller matrices/row vectors. The set of matrices/row vectors need not be exhausted, meaning that some of these matrices/row vectors may not be used in any construction of the given matrix, A.
>
> The matrices are all integer-valued and their second columns are binary, but this is not relevant to problem.
>
> For example, given A and a set U = {A1, A2, A3}, where
> A = [3794 0; 2647 1; 3095 0; 3739 1; 2697 1; 3176 1; 3817 1; 1051 1; 1699 1; 1051 0; 1686 1; 1146 1; 1794 0; 647 1; 1095 0; 1739 1; 697 1; 1176 1; 1817 1; 3051 1; 3699 1; 3051 0; 3686 1; 3146 1]; % (24x2)
>
> and
>
> A1 = [3051 1; 3699 1]; % (2x2)
> A2 = [1051 1; 1699 1]; % (2x2)
> A3 = [3794 0; 2647 1; 3095 0; 3739 1; 2697 1; 3176 1; 3817 1; 1051 0; 1686 1; 1146 1; 1794 0; 647 1; 1095 0; 1739 1; 697 1; 1176 1; 1817 1; 3051 0; 3686 1; 3146 1]; % (20x2)
>
> then A can be constructed (if I typed everything in correctly) via row-aligning A1, A2, A3, as confirmed by:
>
> all(ismember(A, [A1; A2; A3], 'rows')) = 1 % check that the rows of A and its building blocks are the same; order does not matter
>
> The row-intersections of A1, A2, and A3 are empty, meaning that not only can A1, A2, and A3 combine to form A, but there will be no 'pieces' left over. Notice, also, that I don't require an order in the concatenation, only that (1) all of the rows of A1, A2, A3 are used and (2) there is no row-overlap between A1, A2, A3. In short, this makes A a disjoint, independent "union" of A1, A2, and A3. Finally, the matrices in the set U all have less rows than will A.
>
> This was a simple example where the matrix A is not huge, we only had three other matrices to work with, and these matrices were all used up. In general, the matrix is not too large (size(A,1) < 200), but the number of matrices in the set U can increase, with U possibly containing 30 matrices that could possibly be used to "build up" A.
>
> I have coded this successfully already, and now would like to optimize. First I see if each individual matrix in the set U={A1, A2, ... A30} "builds up" to A (would be a rotation of A at this level). Then I do the same for pairs of matrices in U (repeats allowed), (so check if A1 and A1 "build up" to A, A1 and A2, ... A1 and A30, then A2 and A3 and continue), then triplets, etc. I use matlab's combnk function here. The algorithm is "done" when the first amalgamation of A is found.
>
> My algorithm works for smaller-sized matrices, A, and smaller sets of building matrices, U, but is very slow and computationally-intense otherwise. Would anyone please have any ideas how I could optimize this, or suggest a different approach? Thanks!

Any suggestions or ideas? Anyone?

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us