3
votes
0answers
15 views

Looking for an algo to “sorta” diagonalize a similarity matrix.

I've got a big fat similarity matrix. The rows and columns represent people, and the values represent some positive measure of their closeness (0 meaning no connection at all). The n-th row and n-th ...
0
votes
0answers
17 views

How to perform parallel cholesky factorisation

I am a student trying to understand and implement a parallel cholesky factorisation algorithm for sparse matrices in software. Can anyone give an example of a parallel cholesky factorisation ...
1
vote
0answers
50 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
2
votes
0answers
80 views

Quaternion conversion

We have a normalized orthogonal co-ordinate frame travelling through the curve as in figure 1 below, from one end to other. Let us call starting end as A and ending end as B. What we know is initial ...
0
votes
0answers
40 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
2
votes
1answer
42 views

Why is Doolittle Decomposition Algorithm failing and what should I try next?

I am trying to find the LU Decomposition of the following matrix: So far I have only tried the Doolittle Decomposition algorithm with partial pivoting (it's never failed me before!). As far as I can ...
1
vote
0answers
59 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
1
vote
1answer
139 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
0
votes
0answers
29 views

Strassens Matrix Multiplication Algorithm to compute product of 2 4X4 Matrices

Im trying to learn starssens matrix multiplication Algorithm.So far i know that it uses 7 multiplications and replaces a multiplication by several additions and subtractions,to achieve better ...
2
votes
1answer
27 views

The probability of getting a certain image by random pixelation

Well, seeing that I'm terribly bad at math I don't know how to solve this, I'll try to explain, excuse me if I sound dumb. Just suppose that I've got a photo/image with 320x240 resolution and 24 bit ...
1
vote
0answers
28 views

Solving tridiagonal matrices where the top left element is zero

If I have a matrix like this: $$ \left[\begin{array}{rrrrrrrrr|r} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & ...
0
votes
0answers
57 views

QR decomposition algorithm

According to G. W. Stewart (Matrix Algorithms: Volume 1, Basic Decompositions) given an $n\times p$ matrix $A$, let $m=\min\{n,p\}$. The Stewart's Householder triangularization algorithm (Chapter 4, ...
3
votes
3answers
302 views

Solving inhomogenous ODE

I have an inhomogenous ODE. The main issue here is variables are matrices. It is bit of matrix calculus. A solution would be highly appreciated interms of x . I guess we can use same methods for ...
0
votes
2answers
66 views

Determinant of complex matrix

How is the determinant of a complex matrix calculated? Is it the same algorithm as for real matrices, but the determinant itself is complex instead of real? (I was unable to find any hints with ...
2
votes
1answer
57 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
0answers
33 views

Can I solve this problem with matrices?

So I have some two dimensional data sets thats I want to analyse. They can be viewed in 2D form as below: $M1$: $$\begin{matrix}00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 ...
0
votes
0answers
89 views

Finding smaller matrix in bigger matrix

Given a bigger matrix of size R*C .Where each element of matrix is between [-20,20]. Now i need to find a smaller matrix of dimension H*W (H <= R, W <= C) in such a way that sum of squared ...
2
votes
0answers
195 views

How to distribute 5-digit numbers in 5x5 matrices

I have 98000 5-digit numbers, from 00001 to 98000. I need to distribute these 98000 numbers in 14000 5x5 matrices. A matrix cell must contain only a digit from 0 to 9. Each matrix must receive 7 ...
2
votes
0answers
20 views

Ordering binary matrices for reflection/rotation

I have a collection of $n\times n$ binary matrices and I would like to reduce it for symmetry ($D_4$ -- reflections and rotations). The naive method of testing each pair is very slow because the ...
1
vote
1answer
49 views

Computing eigenvalues of principal submatrices of Kronecker product of two PSD matrices

Given two PSD matrices $A \in R^{n \times n}$ and $B \in R^{m \times m}$ with eigenvalues $\lambda_i$ and $\mu_j$ respectively, the eigenvalues of the Kronecker product $A \otimes B$ are given by ...
2
votes
3answers
33 views

Performing matrix chain multiplication by hand

I'm trying to gain intuition for writing a matrix chain multiplication algorithm by working through a few problems by hand. I see plenty of worked-through solutions on sets of three or four solutions, ...
2
votes
3answers
44 views

How to combine Unitary Matrices in a clever way?

I am trying to implement genetic-type algorithms on unitary matrices. Hopefully I should be able to use this question for the mutation part. But I am having an issue with the cross-over step. So here ...
2
votes
2answers
78 views

Algorithm to compute maximum permutation sum in matrix

Given a matrix $A_{n\times n}$ of real numbers, what fast algorithms do there exist to compute the maximum value of $a_{1,\sigma(1)}+a_{2,\sigma(2)}+\ldots+a_{n,\sigma(n)}$ over all permutations ...
0
votes
3answers
51 views

grouping non-zero entries in a matrix according to a rule

I have a matrix say, $a = \left[\matrix{ 0 & 1 & 0& 0& 0& 1& 0\\ 0& 0 &0 &0 &0 &1& 1\\ 1& 0 ...
2
votes
0answers
18 views

Transforms with $O(N \log N)$ Complexity

Beside the Discrete Fourier and Walsh-Hadamard operators, are there any non-trivial, bijective operators that admit an evaluation algorithm of $O(N \log N)$ time complexity or better, whose inverses ...
0
votes
1answer
61 views

Simple algorithm Hermite Normal Form for 3x3

In the scope of the implementation of a model, I need to reduce a 3x3 real matrix into its Hermite Normal Form. I am very new to this kind of reduction and only find algorithm using complex notions ...
0
votes
0answers
56 views

Summing the product of combinations of matrix elements

I have a situation where I have an $NxN$ matrix $A$ where each element $a_{i,j}\in\mathbb{R}_{\leq 0}$. I would like to consider the set of all collections of elements such that each collection of $N$ ...
1
vote
1answer
36 views

matrix row/col mapping

Many square matrices are symmetric. i.e. $a_{i,j}=a_{j,i}$ For such matrices, we can only store the upper triangle elements, i.e. any $a_{i,j}$ for which $i<=j$. Assume a 10x10 matrix. Using this ...
0
votes
0answers
49 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
0
votes
1answer
72 views

Hermite Normal Form and Reduced Row Echelon form.

After reading about the Hermite Normal form and row echelon form, I find it that both these forms are similar in every respect. My question is, are they similar? Or is Hermite Normal form a special ...
2
votes
1answer
66 views

A Matrix Optimization Problem

Given an $n\times d$ matrix $Y$, I am looking for an algorithm to find an $n$-vector $\mathbf{v}$ ($0\le \mathbf{v}_i\le 1$ for all $i$) that minimizes $\sum_{i:X_i<0}X_i$, where $X:= \mathbf{v} ...
0
votes
0answers
19 views

Make the whole matrix zero

Two matrixes with N rows and M columns are given. Let P[i][j] and A[i][j] be the jth element of the ith row of the first and second matrixes respectively. Now we want to make each element of second ...
0
votes
0answers
172 views

Find all possible paths in a Matrix

I'm looking for algorithms to find all paths in a 4 x 4 matrix. The rules are as follows You can move in any direction (up, down, left, right, and diagonally) The next square in the path must be a ...
2
votes
0answers
61 views

Rank Of A Matrix Under Special Conditions

Let A be a $N*N$ matrix. Now A is defined in a special manner: Each row of A is defined by two integers L and R ($0\le L,R\le {N-1}$), such that all elements from the $L^{th}$ to the $R^{th}$ are all ...
0
votes
0answers
49 views

Iteration to Solve Unit Row Diagonally Dominant System

Given a matrix is unit row diagonally dominant $a_{ii}=1>\sum^n_{j=1,j\neq i} |a_{ij}|, \hspace{4mm} 1 \leq i \leq n$, prove that the following iteration will solve $Ax=b$ in the limit. $for ...
0
votes
1answer
72 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
1
vote
0answers
60 views

Transform the array after operations

Given an array A of n numbers we can perform 3 operations on its array elements.Their are n operations in total and ith operation is to be applied on elements from ith index to last element of the ...
1
vote
2answers
59 views

Maze Connectivity

Given a grid maze which is an n × m rectangle maze where each cell is either empty, or is a wall. One can go from one cell to another only if both cells are empty and have a common side. Initially we ...
1
vote
1answer
85 views

White Black Cube

Given a cube of dimension N*N*N made of unit cubic cell and color of each cell could be black or white.I want to find maximum size of subcube which has atleast K% of its cells as black. I want to ...
0
votes
0answers
100 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
3
votes
0answers
705 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
1
vote
1answer
95 views

Efficient Algorithm for Generalized Sylvester's Equation

Is there an efficient computational algorithm for solving the generalized Sylvester's equation: $\displaystyle \sum_{i=1}^{n}A_{i}XB_{i}=C$ The conventional Kronecker product approach to solve this ...
0
votes
1answer
28 views

Need to find N value where each sum A+B is different

I need to find N value (in this case 12, but next time they could more o less) and I need that every sum of two value is a unique number. In the picture below you can see an easy matrix where there ...
0
votes
1answer
76 views

Backward stable algorithm

Assume we have fixed unitary matrices $Q_1, \dots, Q_k \in \mathbb{C}^{m,m}$ and a matrix $A \in \mathbb{C}^{m,n}$ which can be perturbed. How can we proof that the algorithm on computing the product ...
0
votes
0answers
189 views

Operation counts for algorithm using Gaussian elimination to find A^(-1)

I need help determining the operation counts of my algorithm that uses Gaussian elimination to find the inverse of a matrix. Can anyone help me? Here is my algorithm: ...
1
vote
0answers
41 views

Modification of Levinson algorithm for hermitian toeplitz matrix

I have implemented Levinson algorithm for toeplitz matrix by book: Blahut "Fast algorithms for digital signal processing". Book said - modification of this algorithm for hermitian matrixes is simple ...
0
votes
0answers
45 views

Operation count for Tridiagonal System

What is the operation count for solving the tridiagonal system $Ax=b$. I would guess it is $O(n^2)$ because all we are doing is making one sub-diagonal zero all the way across giving us $t(n)=n$ and ...
2
votes
1answer
126 views

Matrix Chain Multiplication Dynamic Equation

I am thinking about the derivation of the following dynamic equation: $$F(n_1,...,n_{k+1};k)=\min_{1<i<k+1}\{n_{i-1}n_i n_{i+1}+F(n_1,...,n_{i-1},n_{i+1},...,n_{k+1};k-1)\}, k=1,...,h$$ Let me ...
2
votes
0answers
90 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
3
votes
1answer
53 views

How is this matrix called (two diagonals)?

I need to write an algorithm for solving this matrix but I wanted to first make a search online and that's why I need its name.