1
vote
0answers
13 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 ...
0
votes
0answers
34 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
14 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
23 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
24 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
56 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
240 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
51 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
38 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
32 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
78 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
182 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
13 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
37 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
31 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, ...
3
votes
3answers
43 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
73 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
54 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
54 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
34 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
48 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
58 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
136 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
45 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
66 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
59 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
57 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
83 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
77 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
613 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
1
vote
1answer
85 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
69 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
182 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
40 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
121 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
85 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
52 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.
1
vote
1answer
128 views

Computing the number of positive and negative eigenvalues

Given a $n \times n$ symmetric matrix $A$ with integers as entries I would like to compute the number of strictly negative $\rm{nn}(A)$ and positive $\rm{np}(A)$ eigenvalues of $A.$ My question is ...
1
vote
1answer
475 views

Prove Solving a Lower Triangular Matrix By Forward Substitution is Backwards Stable

I'm taking a class in scientific computing and we are working on proving stability of certain algorithms. Unfortunately, at this stage, everything is proof-based, and I have little to no experience in ...
1
vote
1answer
156 views

How do deal with a giant sparse matrices?

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I ...
0
votes
0answers
68 views

How to solve this system with conjugate gradient algorithm

CG Algorithm https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!386&v=3 System of equations, the question and the example https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!387&v=3 ...
3
votes
5answers
226 views

How to generate unique id from each element in matrix?

I'm coming from the programming world , and I need to create unique number for each element in a matrix. Say I have a $4\times4$ matrix $A$. I want to find a simple formula that will give each of the ...
1
vote
2answers
1k views

Is there a simple method to do LU decomposition by hand?

Today my professor in numerical analysis pointed out that in the exam we will probably have to do LU decomposition by hand. I'm understand how the decomposition works theoretically, but when it comes ...